Jon Bentleys美丽的快速入门 - 它甚至如何运作？

Question

我认为我对quicksort的工作方式有了很好的理解,直到我在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]以来不会发生交换.最后,我们用m交换l.这搞砸了订单.

我错过了什么吗？

谢谢.

Answer 1

在开头m设置为l,并且元素x[l]被选择为分区元素(pivot).

接下来,算法迭代一个列表,每当它找到一个小于的元素时x[l],它就会在当前之后 移动它m.这意味着,当时m > l,来自l+1to的所有位置上的元素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).