快速排序

快速排序可能是应用最广泛的算法了。快速排序流行的原因是它实现简单、适用于各种不同的输入数据且在一般应用中比其他排序都快得多。
快速排序的特点是，它是原地排序（只需要一个很小的辅助栈），且将长度为N的数组排序所需的时间和NlgN成正比。另外，快速排序的内循环比大多数排序算法都要短小，这意味着它无论是理论上还是实际中都要更快。
主要缺点是非常脆弱，在实现时要非常小心才能避免低劣的性能。在实际应用中要更具实际情况做出改进。

基本算法

快速排序是一种分治的算法，将一个数组分成两个子数组，将两部分独立地排序。在归并排序中，一个数组被等分成两半；在快速排序中，切分（partition）的位置取决于数组的内容。

快速排序：

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]排序
    }
}

该方法的关键在于切分，这个过程使得数组满足以下三个条件：

• 对于某个j，a[j]已经排定；
• a[lo]到a[j-1]中的所有元素都不大于a[j];
• a[j+1]到a[hi]中的所有元素都不小于a[j]。
  我们通过递归地调用切分来排序。

快速排序的切分：

public class Quick {
    private static int partition(Comparable[] a, int lo, int hi) {
        //将数组切分为a[lo..i-1],a[i],a[i+1..hi]  
        int i = lo, j = hi + 1;  //左右扫描指针
        Comparable v = a[lo];
        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] 达成
    }
}

原地切分

如果使用一个辅助数组，我们很容易实现切分，但切分后数组复制回去地开销也许会使我们得不偿失。若不小心将空数组创建写在递归的切分方法中，会大大降低排序的速度。

别越界

切分元素是数组中最小或最大的那个元素，就要小心别让扫描指针跑出数组的边界。partition() 实现可进行明确的检测来预防这种情况。测试条件（j==lo）是冗余的，因为切分元素就是a[lo]，它不可能比自己小。数组右端也有相同的情况，它们都是可以去掉的。

保持随机性

数组元素开始被打乱，这也是保证所有子数组都是随机排序的。（这样主要是对于预测算法的运行时间很重要）。保持随机性的另一种方法是在partition() 中随机选择一个切分元素。

终止循环

正确地检测指针是否越界需要一点技巧。一个最常见的错误是没有考虑到数组中可能包含和切分元素的值相同的其他元素。

处理切分元素值有重复的情况

在有大量重复的值的情况下，左侧扫描最好是在遇到大于等于切分元素值的元素时停下，右侧扫描则是遇到小于等于切分元素值的元素时停下。这样虽然可能会不必要地将一些等值的元素进行交换，但是某些典型应用中，可以避免算法的运算时间达到平方级别。

终止递归

一个常见的错误是不能保证将切分元素放入正确的位置，从而导致程序在切分元素正好是子数组最大或是最小元素时陷入了无限的递归循环当中。

性能特点

快速排序切分方法的内循环会用一个递增的索引将数组元素和一个定值比较。这样比归并排序和希尔排序这样在内循环中移动数据的操作快很多。
快速排序另一个速度优势在于它比较次数很少：
最好情况是每次都能将数组对半分，这种情况下快速排序所用的比较次数正好满足分治递归的C_N=2C_N/2 +N公式。其中，2C_N/2 表示将两个子数组排序的成本，N表示用切分元素和所有数组元素进行比较的成本。这个递归公式的解C_N~Nlg_N。
实际应用中，数组元素可能重复，不难证明即使存在重复元素，算法平均比较次数也不会大于C_N
快速排序有一个潜在的缺点，即每次切分都从很小的（或者很大）的元素进行切分，这样导致一个大子数组需要切分很多次。我们将数组随机化就是尽量避免这种情况。
总的来说，算法的运行时间（本篇中的）在1.38NlgN的某个常数因子范围之内。

算法改进

切换到插入排序

• 对于小数组，快速排序比插入排序慢；
• 因为递归，快速排序的sort()方法在小数组中也会调用自己。
  因此，在排序小数组时应该切换到插入排序。
  将sort()中的语句if(hi<=lo) return;替换成if(hi<=lo+M){Insection.sort(a,lo,hi);return;}
  转换参数M的最佳值是和系统相关的，但是5-15之间的任意值在大多数情况下都能令人满意。

三取样切分

使用子数组的一小部分元素的中位数来切分数组。这样做的代价是需要计算中位数。人们发现将取样大小设为3并用大小居中的元素切分的效果最好。我们还可以将取样元素放在数组末尾作为“哨兵”来去掉partition() 中的数组边界测试。

熵最优的排序

实际中我们会出现大量重复元素的数组。例如，一个元素全部重复的子数组就不需要继续排序了，但我们的算法还会继续将它切分为更小的数组，在有大量重复元素的情况下，快速排序的递归性会使元素全部重复的子数组经常出现，这就有很大的改进潜力，将当前实现的线性对数级的性能提高到线性级别。
一个简单的想法就是将数组切分为三部分，分别对应小于、等于和大于切分元素的数组元素。这种切分实现起来比我们目前使用的二分法更复杂。

三向切分的快速排序：

public class Quick3way {
    private static void sort(Comparable[] a, int lo, int hi) {
        //调用此方法的公有方法sort()见第一个算法
        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++;
        } //现在 a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]成立
        sort(a, lo, lt - 1);
        sort(a, gt + 1, hi);
    }
}