快速排序与三路切分

一、分治的成败全在切分

这一篇对应官方 Lecture 30 & 32（Quick Sort）。

快速排序的骨架和归并排序几乎一样：分区、递归。区别是归并排序在合并时干活，快速排序在切分时干活。

切分做的是这样一件事：选一个轴元素，把数组重新排布成「左边都小于轴、右边都大于轴」，然后返回轴最终落到的位置。之后左右两半各自递归。

于是整个算法的代价被一个量完全决定：切分的均匀程度。

• 如果每次切分都把数组分成两半，递归深度就是 log₂N，总代价 O(N log N)；
• 如果每次切分只分离出一个元素，递归深度就是 N，总代价 O(N²)。

而归并排序不存在这个问题——它的切分点固定在中间，永远均匀。快速排序换来了「原地排序、不需要额外缓冲数组」的便利，代价是把切分的均匀性交给了运气和数据形态。

二、两路切分与它的失效

最朴素的写法是拿最后一个元素当轴，用一个指针把小于轴的元素往左推：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

/** 两路切分，轴取 a[hi]，小于轴的元素往左推 */
static int lomuto(int[] a, int lo, int hi) {
    int pivot = a[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; j++) {
        compares++;
        if (a[j] < pivot) {
            i++;
            swap(a, i, j);
        }
    }
    swap(a, i + 1, hi);
    return i + 1;
}

注意 a[j] < pivot 这个严格小于的判断。它决定了「等于轴的元素」去哪一边：全都留在右边。 这一步是后面两个问题的源头。

用这个切分写快排：

1
2
3
4
5
6
7
8
9
10
11
12
13

/** 末元素为轴的两路快排：只对较小的一侧递归，较大的一侧改成循环，避免深递归 */
static void qsPlain(int[] a, int lo, int hi) {
    while (lo < hi) {
        int p = lomuto(a, lo, hi);
        if (p - lo < hi - p) {
            qsPlain(a, lo, p - 1);
            lo = p + 1;
        } else {
            qsPlain(a, p + 1, hi);
            hi = p - 1;
        }
    }
}

这里的「只对较小的一侧递归、较大的一侧改成循环」是一个必须知道的工程细节。如果两侧都递归，切分退化时递归深度会达到 N，10 万个元素的输入足以让调用栈溢出。改成单侧递归之后，递归深度有了 O(log N) 的上界，而比较次数一点没变。

三、实测：两种失效形态

N = 10000，六种输入形态，三种写法的比较次数：

1
2
3
4
5
6
7

N = 10000 时的键比较次数：
  随机          末元素轴 + 两路 = 151106    随机轴 + 两路 = 158665    随机轴 + 三路 = 164205    
  升序          末元素轴 + 两路 = 49995000    随机轴 + 两路 = 154547    随机轴 + 三路 = 158611    
  降序          末元素轴 + 两路 = 49995000    随机轴 + 两路 = 163260    随机轴 + 三路 = 159199    
  全相等         末元素轴 + 两路 = 49995000    随机轴 + 两路 = 49995000    随机轴 + 三路 = 10000    
  十种取值        末元素轴 + 两路 = 5032318    随机轴 + 两路 = 5032594    随机轴 + 三路 = 37111    
  基本有序        末元素轴 + 两路 = 2065188    随机轴 + 两路 = 158975    随机轴 + 三路 = 155721    

失效形态一：有序输入

升序和降序那两行，末元素轴版本都是 49995000 次比较——正好等于 10000 × 9999 / 2，也就是最坏情况。

原因很直白：升序数组里，最后一个元素是最大值，切分之后它落到最右端，什么都没分出来。下一轮在剩下的 9999 个元素上重复同样的事。每一轮只减少了 1 个元素的规模，总共 N 轮。

「基本有序」那一行 2065188 次是这个缺陷的温和版本：数据大体有序、夹杂少量扰动，切分虽然不至于每次都最差，但依然严重失衡。

修复：随机轴

把「取最后一个」换成「随机抽一个，换到最后一个位置再切」：

1
2
3
4
5
6
7
8

/** 随机轴的两路快排 */
static void qsRandomPivot(int[] a, int lo, int hi) {
    while (lo < hi) {
        swap(a, lo + rnd.nextInt(hi - lo + 1), hi);
        int p = lomuto(a, lo, hi);
        // 同样的单侧递归
    }
}

升序那一行从 49995000 掉到 154547，降序从 49995000 掉到 163260。 效果是决定性的：随机选轴让轴在有序数组里的秩也变成随机的，于是「每次都分出不均匀的两半」从一个必然事件变成了小概率事件。剩下的 154547 与随机输入的 158665 处在同一量级，说明失效形态已经被彻底消除。

失效形态二：大量等值元素

但随机轴救不了等值输入。

全相等那一行，随机轴版本依然是 49995000 次。 原因不在轴选得好不好——不管随机抽到哪个元素，它的值都等于其他所有元素。问题出在 a[j] < pivot 这个判断上：

1
2
3
4

所有元素都等于轴 → 没有任何元素满足 a[j] < pivot
→ 左指针 i 一次也不推进
→ 切分返回 lo，左边空、右边还剩 n-1 个
→ 每轮只消掉一个元素 → N 轮

「十种取值」那一行是这个缺陷的一般形态：5032594 次比较，虽然比全相等好一些，但仍然比随机输入（158665）贵了三十多倍。只有十种取值的数据在实际场景里非常常见——按状态码排序、按年龄段排序、按星期几排序，都属于这一类。

四、三路切分：一次处理完所有等值元素

两种失效形态的根源是同一个：两路切分只会把数组分成「小于轴」和「不小于轴」两块，等值元素被当成「不小于」处理，永远需要再排一次。

三路切分把数组直接分成三块：小于区、等于区、大于区。切完之后，等于区里全是已经就位的元素，它整块跳过、不参与递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

/** 随机轴的三路切分：小于区 / 等于区 / 大于区，等于区整块跳过 */
static void qs3Way(int[] a, int lo, int hi) {
    if (lo >= hi) {
        return;
    }
    int pivot = a[lo + rnd.nextInt(hi - lo + 1)];
    int lt = lo;
    int i = lo;
    int gt = hi;
    while (i <= gt) {
        compares++;
        if (a[i] < pivot) {
            swap(a, lt, i);
            lt++;
            i++;
        } else if (a[i] > pivot) {
            swap(a, i, gt);
            gt--;
        } else {
            i++;
        }
    }
    qs3Way(a, lo, lt - 1);
    qs3Way(a, gt + 1, hi);
}

三个指针的含义可以用一张图理清楚：

flowchart LR
    A["小于区<br/>lo .. lt-1"] --> B["等于区<br/>lt .. i-1"]
    B --> C["未处理区<br/>i .. gt"]
    C --> D["大于区<br/>gt+1 .. hi"]

推进规则只有三条，注意三条各自的下标动作：

大于轴那一支不推进 i 是最容易写错的地方。 从 gt 换过来的元素还没被检查过，如果顺手把 i 往前挪，这个元素就被跳过了。

五、实测：等值数据上的差距

先看等值数据的极端情况。键只有 1、2、3 三种取值，N = 10000：

1
2
3
4

三路切分对等值块的剪枝效果（N = 10000，键只有 1..3 三种取值）：
  末元素轴 + 两路：比较 = 16692168，移动 = 33296，升序 = true
  随机轴 + 两路：比较 = 16675438，移动 = 60000，升序 = true
  随机轴 + 三路：比较 = 16691，移动 = 13382，升序 = true

16692168 对比 16691，相差 1000 倍。

这个差距不是常数优化，而是算法量级的变化：

「全相等」那一行尤其干净：三路切分只需要 10000 次比较——正好是 N，一次扫描确认所有元素都等于轴，然后等于区覆盖整个数组，递归两侧都是空区间。这已经是理论下限了，任何基于比较的排序都不可能用少于 N−1 次比较确认 N 个元素已有序。

不过三路切分也不是免费的。回到随机输入那一行：

在没有重复键的数据上，三路切分反而略贵。 因为每个元素都要走一遍三条分支的判断，而等值区往往小得没有收益。这是一个典型的「用额外判断换最坏情况保障」的取舍。

六、工程上的两个细节

除了前面提到的单侧递归，真实实现里还有两个值得知道的点。

其一：小数组切换成插入排序。 递归到规模很小的子数组时，快速排序的函数调用开销已经超过了它省下的比较次数。而小数组往往接近有序，插入排序在这种输入上只需要线性的比较次数——正好互补。所以工业级实现普遍会设一个阈值（常见是 8 到 16 个元素），低于它就直接用插入排序收尾。

其二：处理等值元素的策略取决于数据。 如果确定数据里的键几乎不重复，两路切分更划算；只要存在大量重复键的可能，就应该上三路切分。判据很实际：

七、小结

三条能带走的：

1. 同一句「这是 O(N log N) 的算法」可能掩盖一个数量级的失效。 快速排序在有序输入和等值输入上都会退化到 O(N²)，而这两种输入在真实数据里都非常常见，不是构造出来的边角情况。
2. 随机化只解决「轴选得不好」，不解决「切分本身装不下信息」。 随机轴彻底修好了有序输入的退化，对等值输入却毫无帮助——因为问题不在轴的选择，而在两路切分只有两个出口，装不下「等于轴」这第三种情况。
3. 先看数据的键分布，再决定切分方式。 「键几乎不重复」和「键集中在少数取值上」对应两种不同的写法，选错了不会报错，只会在性能上悄悄差出两个数量级。