1

以下是Hoare我编写的分区算法，用于根据给定的枢轴对数组进行分区（在这种情况下，它是数组的第一个元素，一个相当糟糕的选择！）。但是，Bentley-McIlroy 3-way partitioninghttp ://www.sorting-algorithms.com/static/QuicksortIsOptimal.pdf声称当键数相等时可以提供更好的性能。谁能简要解释第 9 页上的代码实现了什么，以及为什么它比Hoare算法执行得更好？还有一个问题，分区基于 和 放置<元素。如果多次出现的元素不是枢轴怎么办？=>

def hoare(arr,start,end):
     pivot = arr[start]
     i,j = start,end
     while i < j:
        while i < j and arr[i] <= pivot:
            i += 1
        while j >= i and arr[j] > pivot:
            j -= 1
        if i < j:
            arr[i],arr[j] = arr[j],arr[i]
     arr[start],arr[j] = arr[j],arr[start]
     return j
4

2 回答 2

5

我发现可以根据 N. Lumoto 的想法来实现 3-way partition，这更容易一些。（正如 Jon Bentley 在他的《Programming Pearls》一书中提到的，Lumoto 的方法很简单）。

这个想法是在扫描期间保持不变，即在任何时候小于枢轴的元素都放在最左边的部分，而等于枢轴的元素在该部分的旁边，大于的元素枢轴放在最右边。剩下的部分是那些元素还没有被检查过。

这些部分以i、k和为界j。当我们检查一个元素时，如果它等于pivot，我们就前进到下一个，如果它小于pivot，我们可以将它与'equal'部分的第一个交换，这样不变量可以是恢复。否则，我们需要继续与更大部分前面的最后一个交换它。

/*
 * Another 3-way partition ternary quick sort based on N. Lomuto's method.
 *   Invariant: ... less ... | ... equal ... | ... ? ... | greater |
 *                           i               k           j
 */
void qsort3(Key* xs, int l, int u) {
    int i, j, k; Key pivot;
    if (l < u - 1) {
        i = l; j = u; pivot = xs[l];
        for (k = l + 1; k < j; ++k) {
            while (pivot < xs[k]) { --j; swap(xs[j], xs[k]); }
            if (xs[k] < pivot) { swap(xs[i], xs[k]); ++i; }
        }
        qsort3(xs, l, i);
        qsort3(xs, j, u);
    }
}

我针对标准库中的 qsort API 用 100,000 个元素测试了这个程序。

于 2013-03-12T08:30:00.973 回答
4

我认为第 9 页的代码在第 8 页的图表中得到了很好的解释：您首先进行分区，但还将等于枢轴的元素交换到向量的边缘，因此最终结果为：

[equals-left] [lesses] [greaters] [equals-right]

然后将相等的元素交换回中心：

[lesses] [equals-left] [equals-right] [greaters]

然后你递归排序[lesses]和[greaters]

Sedgwick 的假设是数据集中有许多重复的元素。在这种情况下，重复枢轴是很常见的，如果是这样，您可以通过在任何一个快速排序递归中不包括任何枢轴的重复来获得一些好处，以便总和的大小两个分区的大小将小于向量的大小，减去枢轴的重复次数（即使它只是单独的）。这减少了您需要递归的元素数量，从而使递归更快。

这样做的代价是每个元素进行一到两次额外比较，尽管它们都只是重复先前的比较，但成功条件不同。在比较复杂的情况下，您可能希望使用显式的三向比较函数，以便能够保存最后一个 < 比较的结果（在 Sedgwick 代码的 while 循环中）。如果不重复枢轴，那么这正是额外的成本：那些额外的比较。如果重复主元，则对于每个重复的主元元素，有一个或两个额外的交换和两个或一个额外的比较（所以三个额外的操作，如果交换和比较花费相同的时间），加上每个重复的主元元素的两个额外比较其他元素。

这值得吗？我持怀疑态度，但如果 Sedgwick 这么说，那么你应该听他的，而不是听我的。

于 2012-09-25T16:54:04.760 回答