Bentley-McIlroy 三路分区

Question

以下是Hoare我编写的基于给定主元对数组进行分区的分区算法（在这种情况下，它是数组的第一个元素，一个相当糟糕的选择！）。然而，Bentley-McIlroy 3-way partitioning在http://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

Answer 1

我发现可以根据N. Lumoto的想法实现3路分区，简单一点。（正如 Jon Bentley 在他的《编程珍珠》一书中提到的，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);
    }
}

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