quicksort特殊情况 – 似乎是K＆R的错误算法

我在解决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提前谢谢！

Answer 1

循环left + 1到right 包括 。 当i=4 ，测试失败并且last没有增加。

然后递归调用使用left=0,right=2和left=4,right=4对BACDE进行排序。 （当D是枢轴时，这是正确的。）

Answer 2

好吧，你的输入子arraysACBE已经被D划分（ ACB小于D且E大于D ），所以分区周期不会物理交换任何值也就不足为奇了。

实际上，说它“无所作为”是不正确的。 它不会重新排序循环中的任何内容，因为您的输入数据不需要额外的重新排序。 但它仍然做一件事：它找到last的值，表示较小的元素结束和较大的元素开始，即它将ACBE分为ACB和E部分。 循环以last == 3结束，这是进一步递归步骤​​的分区点。