关于 Fast 3 Way Partition 中的排序数据/通过 Sedgewick 进行快速排序

Question

我对 quickSort 中的 3 路分区感兴趣 http://algs4.cs.princeton.edu/23quicksort/Quick3way.java.html 因为它使用该分区来克服就地快速排序中的荷兰国旗问题（相等数据）。由于作者是 Sedgewick，我会假设该代码没有错误，但选择的基准很容易出现排序数据的最坏情况 n^2 时间复杂度。

根据维基百科：

In the very early versions of quicksort, the leftmost element of the partition would often be chosen as the pivot element. Unfortunately, this causes worst-case behavior on already sorted arrays, which is a rather common use-case. The problem was easily solved by choosing either a random index for the pivot, choosing the middle index of the partition or (especially for longer partitions) choosing the median of the first, middle and last element of the partition for the pivot (as recommended by Sedgewick).[17]

快速排序代码：

 // quicksort the subarray a[lo .. hi] using 3-way partitioning
private static void sort(Comparable[] a, int lo, int hi) { 
    if (hi <= lo) return;
    int lt = lo, gt = hi;
    Comparable v = a[lo];
    int i = lo;
    while (i <= gt) {
        int cmp = a[i].compareTo(v);
        if      (cmp < 0) exch(a, lt++, i++);
        else if (cmp > 0) exch(a, i, gt--);
        else              i++;
    }

    // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]. 
    sort(a, lo, lt-1);
    sort(a, gt+1, hi);
    assert isSorted(a, lo, hi);
}

我将中音或九音用作轴心是否正确，还是我错过了什么？我知道这是指导性的，但为什么不至少使用中音呢？

编辑

改组是否被认为是一种严格的方法来防止最坏的情况而不是简单地选择更好的主元？为什么不直接改变主元...用显着的随机性对一个大数组进行洗牌会花费一些开销，不是吗？既然洗牌算法需要额外的时间，为什么不选择主元呢？例如，将数据与所有等效数据混洗完全是一种浪费。运行 isSorted 在数组上作为一种启发式方法，需要对等量数据进行编辑，这不是更好吗？ – 不是要与 Hoare 争论的人，但是检查 ifSorted 是否会更好地检查 ifSorted 并修改会短路的等效数据而不是运行不必要地通过排序的数据？这将花费与随机播放相同的时间。

Answer 1

您引用的 sort 方法是一个 private 辅助方法。真正的public方法sort是这样的：

public static void sort(Comparable[] a) {
    StdRandom.shuffle(a);
    sort(a, 0, a.length - 1);
    assert isSorted(a);
}

通过调用 StdRandom.shuffle，数组在进行快速排序之前被随机打乱。这是防止最坏情况的方法。

它不仅用于这种 3 路分区快速排序，它还用于普通快速排序。

引用 Sedgewick 的 Algorithms 一书，§2.3 QUICKSORT

Q. Randomly shuffling the array seems to take a significant fraction of the total time for the sort. Is doing so really worthwhile?

A. Yes. It protects against the worst case and makes the running time predictable. Hoare proposed this approach when he presented the algorithm in 1960—it is a prototypical (and among the first) randomized algorithm.

关于 Fast 3 Way Partition 中的排序数据/通过 Sedgewick 进行快速排序

Regarding sorted data in Fast 3 Way Partition / in place quicksort via Sedgewick

sorting

algorithm

quicksort