Jon Bentley 漂亮的快速排序 - 它是如何工作的？

Question

我以为我对快速排序的工作原理有很好的了解，直到我观看了 http://code.google.com/edu/algorithms/index.html 上的视频，其中 Jon Bentley 介绍了他的“漂亮的快速排序代码”，其中如下：

void quicksort(int l, int u){
    int i, m;
    if(l >= u) return;
    m = l;
    for(i = l+1; i<= u; i++)
        if(x[i] < x[l])
            swap(++m, i); //this is where I'm lost. Why the heck does it preincrement?

    swap(l, m);

    quicksort(l, m-1);
    quicksort(m+1, u);

}

令我困惑的算法的另一个部分是 FOR 循环之后的最终交换。为什么这是必要的？假设数组已经按顺序排列。如果这是真的，则由于 x[i] > x[l]，因此不会发生交换。最后，我们将 l 与 m 交换。这搞乱了顺序。

我错过了什么吗？

谢谢。

Answer 1

一开始，

m

设置为

l

，并且选择元素

x[l]

作为分区元素（枢轴）。

接下来，该算法迭代列表，每当发现小于

x[l]

的元素时，就会将其移动到 就在当前

m

之后。 这意味着，当

m > l

时，从

l+1

到

m

的所有位置上的元素都小于元素

x[l]

。

例如：

3 5 4 2 1  l = 0, m = 0, i = 1
  ^
3 5 4 2 1  l = 0, m = 0, i = 2
    ^
3 2 4 5 1  l = 0, m = 1, i = 3
      ^
3 2 1 5 4  l = 0, m = 2, i = 4
        ^

最后，我们将最后一个较小的数字与第一个（分区）元素交换以获得：

1 2 3 5 4

如果没有比第一个更小的元素，则交换不会执行任何操作（因为

m

等于

l

）。

Answer 2

x[l]

处的元素是所选的枢轴。 for 循环的不变性是，所有从

x[l+1]

到

x[m]

的元素都小于主元，并且从

x[m]

到

x[i]

的所有元素都大于或等于主元。

当它找到小于枢轴的元素时，会将其向下移动到条目

m+1

，然后向上移动

m

。 （

m+1

处的入口比枢轴大，因此向上移动就可以了。）

最后一个交换是将枢轴从

x[l]

移动到

x[m]

，因为它需要位于下部阵列和上部阵列之间。如果没有发生交换（排序数组示例），则

m==l

和最终交换不会移动任何内容。

设置

m = l + 1

并使用

m++

而不是

++m

，代码在教学上会更清晰。

Answer 3

分区算法不错，也容易记住。它曾出现在《Communications of ACM》杂志上，并被 Bentley 多次重述。它也出现在 Bentley 的《Programming Pearls》一书中。 这个想法是跟踪否定后置条件的元素，即枢轴后面的元素较少，索引上方的元素较大。但是，如果选择的随机元素不是随机的，我们最终可能会得到最大（或最小）的元素，这将使我们需要对 O(n) 进行更多的交换。 Java 中的实现和解释是here。
如果数组已排序，m 永远不会改变其初始值 l，因此交换不会执行任何操作。

Answer 4

固定索引

l

Answer 5

u

分别指向要排序的子数组的第一个和最后一个元素。始终选择值

x[l]

作为主元。在循环顶部，子数组（不包括主元

x[l]

）划分如下：

下部区域：索引为

l < index <= m

的元素已经过测试，发现为

< x[l]
• 中间区域：索引为

  m < index < i

  的元素经过测试，发现为
>= x[l]
• 上部区域：索引为

  i <= index <= u

  的元素尚未经过测试

• 一个可能造成混淆的原因是，当循环运行时，值大于枢轴的区域是

  中间
部分，而不是上面的部分。在未测试的区域耗尽之前，它不会到达阵列的上部 - 通过重复交换，它被有效地“移动”，为扩展的下部区域腾出空间。

具体来说，每当下部区域需要扩展时，循环变量m就会预先递增：中间区域的第一个元素（如果有）必须移动到末尾，以便扩展下部区域。请注意，如果中间区域为空，则预递增后的

m == i

（对于这种情况，

swap()

操作必须是空操作）。最后，枢轴

x[l]

被交换到下部区域的末端，以将其放置在递归步骤中。请注意，如果数组已经按顺序排列，则下部区域为空，

m == l

，最后的

swap()

操作又是无操作。