3

我在理解 K&R 的快速排序算法（没有指针的简化版本）时遇到问题。Dave Gamble here已经提供了详尽的解释说明。但是我注意到，通过从一个稍微改变的字符串开始，我们可以在 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

最后=左=0

i = 1 if ( v 1 < v[0] ) 这是真的，所以我们将 v 1（因为 last 在操作之前递增）与 v 1交换，所以没有任何变化，last = 1，仍然有 DACBE；

现在 i = 2 if ( v[2] < v[0] ) -> true 所以我们将 v[2] 与 v[2] 交换，没有任何改变；最后 = 2

现在 i = 3 if ( v[3] < v[0] ) -> true 所以我们用 v[3] 交换 v[3] 没有任何改变 AGAIN (!), last = 3

所以显然出了点问题，算法什么也没做。非常感谢您的意见。我一定是错的，作者比我好；D提前谢谢！

4

2 回答 2

3

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

然后递归调用BACDE用left=0,right=2and排序left=4,right=4。D（当枢轴出现时这是正确的。）

于 2012-08-13T17:29:25.773 回答
2

好吧，碰巧您的输入子数组ACBE已经被D(ACB小于D和E大于D) 分区，因此分区周期没有物理交换任何值也就不足为奇了。

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

于 2012-08-13T17:29:10.733 回答