"贝特利-麦克罗伊三分区"

Question

下面是我编写的Hoare分区算法，用于根据给定的轴对数组进行分区（在本例中，它是数组的第一个元素，这是一个相当糟糕的选择！）。然而，在http://www.sorting-algorithms.com/static/QuicksortIsOptimal.pdf处的Bentley-McIlroy 3-way partitioning声称在密钥数目相等时可以提供更好的性能。有人能简单地解释一下第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

Answer 1

我认为，第9页的代码在第8页的图表中解释得很好：首先进行分区，然后将与轴相等的元素交换到向量的边上，因此结果是：

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

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

^{2}$

然后递归排序[lesses]和{}

Sedgwick的假设是数据集中有许多重复的元素。在这种情况下，轴心被重复是很常见的，如果是这样的话，你可以通过不在任何一个快速排序递归中包含轴心的任何重复来获得一些好处，这样两个分区之和的大小将小于矢量的大小乘以轴心的重复次数（即使它只是这减少了需要递归的元素的数量，这使得递归更快。在

这样做的成本是每个元素一到两个额外的比较，尽管两个元素都只是用不同的成功条件重复前面的比较。在比较比较比较复杂的情况下，您可能需要使用显式的三向比较函数，以便能够保存上一次<；比较的结果（在Sedgwick代码中的while循环中）。如果这个支点没有重复，那就是额外的成本：那些额外的比较。如果pivot是重复的，那么每个重复的pivot元素有一个或两个额外的交换和两个或一个额外的比较（因此，如果swap和compare花费相同的时间，则需要三个额外的操作），再加上每个其他元素的两个额外比较。在

这值得吗？我很怀疑，但如果塞奇威克说是的话，那你应该听他的，而不是我。在

Answer 2

我找到了一个更容易实现的方法。（正如Jon Bentley在他的《编程珍珠》（Programming pearls）一书中提到的，Lumoto的方法很简单）。在

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

这些部分由i，k，j所限定。当我们检查一个元素时，如果它等于轴，我们就前进到下一个元素，如果它小于轴，我们可以将它与“相等”部分上的第一个元素交换，这样就可以恢复不变量。否则，我们需要在更大的区域前继续与最后一个交换。在

/*
 * Another 3-way partition ternery 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);
    }
}

我用100000个元素对标准库中的qsortapi测试了这个程序。在