快速排序

简介

快速排序是一种分治的排序算法。它将一个数组分成两个子数组，将两部分独立地排序。

快速排序和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序将数组排序的方式则是当两个子数组都有序时整个数组也就自然有序了。在第一种情况中，递归调用发生在处理整个数组之前；在第二种情况中，递归调用发生在处理整个数组之后。在归并排序中，一个数组被等分为两半；在快速排序中，切分（partition）的位置取决于数组的内容。

基本算法

下面直接给出快速排序的基本算法，其中有些函数方法为普林斯顿大学的API，请点这里。

public class Quick {
    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a);        // 消除对输入的依赖
        sort(a, 0, a.length - 1);
    }

    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);            // 将左半部分a[lo .. j - 1]排序
        sort(a, j + 1, hi);            // 将右半部分a[j + 1 .. hi]排序
    }

    // 将数组切分为a[lo..i-1], a[i], a[i+1..hi]
    private static int partition(Comparable[] a, int lo, int hi) {
        int i = lo, j = hi + 1;        // 左右扫描指针
        Comparable v = a[lo];        // 切分元素

        // 扫描左右，检查扫描是否结束并交换yuans
        while (true) {
            while (less(a[++i], v)) {
                if (i == hi) {
                    break;
                }
            }

            while (less(v, a[--j])) {
                if (j == lo) {
                    break;
                }
            }

            if (i >= j) {
                break;
            }

            exch(a, i, j);
        }

        exch(a, lo, j);            // 将v = a[j]放入正确的位置
        return j;                // a[lo..j-1] <= a[j] <= a[j+1..hi]达成
    }
}

算法改进

切换到插入排序

• 对于小数组，快速排序比插入排序慢；
• 因为递归，快速排序的sort()方法在小数组中也会调用自己。

简单改动上面的代码就可以实现，将sort()中的语句：

if (hi < lo) {
    return;
}

替换成下面这条语句来对小数组使用插入排序：

if (hi <= lo + M) {         // 转换参数M的最佳值是和系统相关的，一般在5~10之间
    Insertion.sort(a, lo, hi);
    return;
}

三取样切分

改进快速排序性能的第二个办法是使用子数组的一小部分元素的中位数来切分数组。这样做得到的切分更好，代价是需要计算中位数。人们发现将取样大小设为3并用大小居中的元素切分的效果最好。

熵最优排序

主要针对于实际应用中经常会出现含有大量重复元素的数组。一个简单的想法是将数组切分为三部分，分别对应小于、等于和大于切分元素的数组元素。

public class Quick3way {
    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }

        int lt = lo, i = lo + 1, gt = hi;
        Comparable v = a[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++;
            }
        }

        sort(a, lo, lt - 1);
        sort(a, gt + 1, hi);
    }
}