6-Quicksort

快速排序

快排是20世纪十大算法之一。实际应用中快排的综合速度最快。

基本思想

1. 对数组进行 Shuffle
2. 对于某个给定的元素，将所有比其小的放在它左边，比其大的放在它右边
3. 对左右两部分分别进行递归排序

代码实现

• i从左往右找到第一个大于基准元素的
• j从右往左找到第一个小于基准元素的
• 交换i和j
• 直到i到j的右侧，此时j的位置就是基准元素应该放置的位置，交换基准元素和j

public class Quick {
    /**
     * Rearranges the array in ascending order, using the natural order.
     * @param a the array to be sorted
     */
    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a);
        sort(a, 0, a.length - 1);
        assert isSorted(a);
    }

    // quicksort the subarray from a[lo] to a[hi]
    private static void sort(Comparable[] a, int lo, int hi) { 
        if (hi <= lo) return;
        int j = partition(a, lo, hi);
        sort(a, lo, j-1);
        sort(a, j+1, hi);
        assert isSorted(a, lo, hi);
    }

    // partition the subarray a[lo..hi] so that a[lo..j-1] <= a[j] <= a[j+1..hi]
    // and return the index j.
    private static int partition(Comparable[] a, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        Comparable v = a[lo];
        while (true) { 

            // find item on lo to swap
            while (less(a[++i], v)) {
                if (i == hi) break;
            }

            // find item on hi to swap
            while (less(v, a[--j])) {
                if (j == lo) break;      // redundant since a[lo] acts as sentinel
            }

            // check if pointers cross
            if (i >= j) break;

            exch(a, i, j);
        }

        // put partitioning item v at a[j]
        exch(a, lo, j);

        // now, a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
        return j;
    }
}

实现细节

• 原地排序，不需要额外空间
• 要注意何时停止循环，这是一个比较棘手的点
• (j == lo)其实是多余的
• Suffle 非常有必要！如果对已经排好序的数组使用快排，复杂度将会高至$N^2$。因此使用 Suffle 可以保证性能。
• 快排不稳定

复杂度分析

命题：对长度为N的数组使用快排需要 ~ $2NlnN$的比较次数和 ~$\frac13NlnN$的交换次数

证明：

改进空间

1. 小数组采用插入排序（和 mergesort 改进方法一样）

2. 基准值尽量选择处于中间的元素

快速选择

我们希望能够快速选择出一个数组第$k$小的元素。快速选择的上界是 $NlogN$（做一个快速排序再选择），下界是$N$（至少需要遍历整个数组）。借助快排的思想不难实现。

代码实现

    public static Comparable select(Comparable[] a, int k) {
        if (k < 0 || k >= a.length) {
            throw new IllegalArgumentException("index is not between 0 and " + a.length + ": " + k);
        }
        StdRandom.shuffle(a);
        int lo = 0, hi = a.length - 1;
        while (hi > lo) {
            int i = partition(a, lo, hi);
            if      (i > k) hi = i - 1;
            else if (i < k) lo = i + 1;
            else return a[i];
        }
        return a[lo];
    }

复杂度

• 快速选择平均需要线性时间

• 简单证明：

  • 

• 如果选择之前不 Suffle 那么最坏情况为$\frac12N^2$

三路快速排序

如果数组中有多个重复元素，那么快速排序可以继续优化。有些快排的实现在面对拥有大量重复元素的数组时复杂度将会达到平方量级！

基本思想

我们希望能够将数组分成三部分：

做法：

1. 赋值 v 为 a[lo]

2. i 从小到大递增

   1. a[i] < v 则交换 a[lt] 和 a[i]；lt 和 i 递增
   2. a[i] > v 则交换 a[gt] 和 a[i]；gt 递减
   3. a[i] == v 则 i 递增

代码实现

public class Quick3way {

    /**
     * Rearranges the array in ascending order, using the natural order.
     * @param a the array to be sorted
     */
    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a);
        sort(a, 0, a.length - 1);
        assert isSorted(a);
    }

    // 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 + 1;
        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);
    }

}

复杂度分析

不同系统的排序

Java

• 对于对象数组采用 mergesort，对于基本数据类型采用 quicksort，不同的数据类型拥有不同的比较方式。

C qsort

早期的 c 内置 qsort 经常会出现运行缓慢的问题

目前广泛运用的排序思想

• 小数组排序用插入排序

• 使用三路快速排序

• 基准元素选择方法：

  • 小数组：中间元素
  • 中等大小数组：3个元素的中位数
  • 大型数组：Tukey’s ninther

Tukey’s ninther

选择三组，每组三个元素，分别取三组元素的中位数，然后去三个中位数的中位数作为基准元素。

选择排序时需考虑的因素

各种排序方法比较