3

我以为我对快速排序的工作原理有很好的了解，直到我在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 交换。这搞砸了订单。

我错过了什么吗？

谢谢。

4

5 回答 5

6

在开始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）。

于 2012-04-06T21:51:09.090 回答
1

at 的元素x[l]是所选的枢轴。for 循环的不变量是所有元素x[l+1]throughx[m]都小于枢轴，并且所有来自x[m]through的元素x[i]都大于或等于枢轴。

当它找到一个小于枢轴的元素时，它将它向下移动到 entry m+1，然后向上碰撞m。（入口处m+1大于枢轴点，因此向上移动它很好。）

最后一个交换是将枢轴从x[l]to移动，x[m]因为它需要在下部数组和上部数组之间结束。如果没有发生交换（排序数组示例），那么m==l最终交换不会移动任何东西。

代码在教学上会更清晰地设置m = l + 1和使用m++，而不是++m.

于 2012-04-06T21:50:57.620 回答
1

分区算法很好并且容易记住。它已经在 ACM 的通信中或被 Benltey 多次重述。它也出现在 Bentley 的 Programming Pearls 书中。这个想法是跟踪否定后置条件的元素，即枢轴后面的元素较少，索引较高的元素较大。但是，如果选择随机元素不是随机的，我们最终可能会得到最大（或最小）的元素，这将使我们对 O(n) 进行更多的交换。java中的一个实现和解释是[博客]：http ://harisankar-krishnaswamy.blogspot.in/2013/05/quick-sort-partition-algorithm.html “这里”

哈里

于 2013-05-19T04:36:59.233 回答
0

如果数组已排序，m 永远不会从它的初始值 l 改变，所以交换什么也不做。

于 2012-04-06T21:53:30.710 回答
0

固定索引l并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()操作再次为空操作。

于 2012-04-06T22:40:54.650 回答