2.3 快速排序 Quick Sort

优点：

• 原地排序
• 将长度为 N 的数组排序所需的时间和 NlogN 成正比
• 内循环比大多数排序算法都要短（更快）
  缺点：
• 非常脆弱，在实现中要非常小心才能避免低劣的性能

基本算法

快速排序是一种分治的排序算法。将一个数组分成两个子数组，将两部分独立地排序。快速排序和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的字数组归并以将整个数组排序；而快速排序将数组排序的方法则是当两个子数组都有序了整个数组也就自然有序了。归并排序中，递归调用发生在处理整个数组之前，快速排序中，递归调用发生在处理整个数组之后。在归并排序中，一个数组杯等分为两半；在快速排序中，切分 partition 的位置取决于数组的内容。

快速排序示意图

# Python
def quick_sort(array, lo, hi):
    if lo < r:
        p = partition(array, lo, hi)
        quick_sort(array, lo, p - 1)
        quick_sort(array, p + 1, hi)
 
def partition(array, lo, hi):
    x = array[r]
    i = lo - 1
    for j in range(lo, hi):
        if array[j] <= x:
            i += 1
            array[i], array[j] = array[j], array[i]
    array[i + 1], array[hi] = array[hi], array[i+1]
    return i + 1

切分过程总是能排定一个元素，用归纳法不难证明递归能够正确地将数组排序；如果左子数组和右子数组都是有序的，那么由左子数组（有序且没有任何元素大于切分元素），切分元素，和右子数组（有序且没有任何元素小于切分元素）组成的结果数组也一定是有序的。

需要实现切分方法：

1. 随意地取 a[lo] 作为切分元素，即哪个将会被排定的元素
2. 从数组的左端开始向右扫描直到找到一个大于等于它的元素
3. 再数组的右段开始向左扫描直到找到一个小于等于它的元素
4. 交换它们的位置
5. 如此继续，可以保证左指针 i 的左侧元素都不大于切分元素，右指针 j 的右侧元素都不小于切分元素
6. 当两个指针相遇时，将切分元素 a[lo] 和左子数组最右侧的元素 a[j] 交换然后返回 j

快速排序的切分示意图

// Java
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]

    }

# Python
def partition(array, lo, hi):
    x = array[r]
    i = lo - 1
    for j in range(lo, hi):
        if array[j] <= x:
            i += 1
            array[i], array[j] = array[j], array[i]
    array[i + 1], array[hi] = array[hi], array[i+1]
    return i + 1

切分轨迹（每次交换前后的数组内容）

• 原地切分
• 别越界
• 保持随机性
  数组元素的顺序是被打乱过的。保持随机性的另一种方法是在 partition() 中随机选择一个切分元素。
• 终止循环
• 处理切分元素值有重复的情况
  左侧扫描最好是在遇到大于等于切分元素值的元素时停下，右侧扫描则是遇到小于等于切分元素值的元素是停下。尽管这样可能会不必要地将一些等值的元素交换，但在某些典型应用中，它能够避免算法的运行时间变为平方级别。
• 终止递归

性能特点

快速排序切分方法的内循环会用一个递增的索引将数组元素和一个定值比较。
快速排序另一个速度优势在于它的比较次数很少。排序效率最终还是依赖切分数组的效果，而这依赖于切分元素的值。
快速排序的最好情况是每次都正好能将数组对半分。
潜在缺点: 在切分不平衡时这个程序可能会极为低效。要在快速排序前将数组随机排序的主要原因就是要避免这种情况。

算法改进

切换到插入排序 insertion sort

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

if (hi <= lo) return;

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

if (hi <= lo + M) {Insertion.sort(a, lo, hi); return;}

三区样切分

使用子数组的一小部分元素的中位数来切分数组。将取样大小设为 3 并用大小居中的元素切分的效果最好。

熵最优的排序

将数组切分为三部分，分别对应小于，等于，和大于切分元素的数组元素。
快速现象切分（3-way partition）

待完续