我在解决K&R的快速排序算法(没有指针的简化版本)时遇到了问题。 Dave Gamble在此解释已经有了彻底的解释 。 但是我注意到,从稍微改变的字符串开始,我们可以在for循环的许多循环中获得没有交换。 首先是代码:
void qsort(int v[], int left, int right) { int i, last; void swap(int v[], int i, int j); if (left >= right) /* do nothing if array contains */ return; /* fewer than two elements */ swap(v, left, (left + right)/2); /* move partition elem */ last = left; /* to v[0] */ for (i = left + 1; i <= right; i++) /* partition */ if (v[i] < v[left]) swap(v, ++last, i); swap(v, left, last); /* restore partition elem */ qsort(v, left, last-1); qsort(v, last+1, right); }
我认为演练:
我们从CADBE开始; 左= 0; 右= 4; D是枢轴因此根据算法我们将D与C交换获得DACBE
last = left = 0
i = 1如果(v 1 <v [0])为真,那么我们交换v 1 (因为last在运行前递增)与v 1因此没有变化,last = 1,仍然有DACBE;
现在i = 2 if(v [2] true所以我们用v [2]交换v [2]再没有改变; 最后= 2
现在i = 3 if(v [3] true所以我们用v [3]交换v [3]没有改变AGAIN(!),last = 3
显然有些事情是错误的,算法什么都不做。 你的意见非常赞赏。 我一定是错的,作者比我好; D提前谢谢!
循环left + 1
到right
包括 。 当i=4
,测试失败并且last
没有增加。
然后递归调用使用left=0,right=2
和left=4,right=4
对BACDE
进行排序。 (当D
是枢轴时,这是正确的。)
好吧,你的输入子arraysACBE
已经被D
划分( ACB
小于D
且E
大于D
),所以分区周期不会物理交换任何值也就不足为奇了。
实际上,说它“无所作为”是不正确的。 它不会重新排序循环中的任何内容,因为您的输入数据不需要额外的重新排序。 但它仍然做一件事:它找到last
的值,表示较小的元素结束和较大的元素开始,即它将ACBE
分为ACB
和E
部分。 循环以last == 3
结束,这是进一步递归步骤的分区点。
以上就是c/c++开发分享quicksort特殊情况 – 似乎是K&R的错误算法相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/541666.html