8.2　快速排序：平均最快，最坏要防

学习目标：学完本节，你能

• 手写快速排序的分区操作，并说清它的工作原理；
• 解释最坏情况 $O(n^2)$ 是怎么产生的，以及它为什么比想象中更容易触发；
• 用随机化基准和三数取中把最坏情况"打散"；
• 说清快排相对归并排序的取舍。

先修：8.1（归并排序）、2.4（分治）。 固定术语：快速排序、基准、分区、最坏情况退化。 环境与版本：.NET 8 / C# 12。 预计阅读：34 分钟。

一、直觉：把小的放左边，大的放右边

归并排序的思路是"先切开、排好、再合并"。快速排序反过来：

先做一件大事（把数组整理成"左边都小、右边都大"），然后两边各自递归。

这件"大事"叫分区（Partition）：

1. 从数组里挑一个元素当基准（pivot）
2. 把所有比基准小的放到它左边
3. 把所有比基准大的放到它右边
4. 基准自己就位了 —— 它的位置就是最终位置，以后不用再动

分区前:  [3, 8, 1, 9, 2, 7]      基准 = 7（最后一个）
分区后:  [3, 1, 2]  [7]  [8, 9]
          ↑都小于7   ↑就位  ↑都大于7

然后对 [3,1,2] 和 [8,9] 分别递归做同样的事。

关键区别：

最后一行就是快排的软肋。

二、实现

/// <summary>分区（Lomuto 方案）：返回基准元素的最终位置。</summary>
static int Partition(int[] a, int lo, int hi, ref long cmp, ref long swaps)
{
    int pivot = a[hi];                    // 基准取最后一个元素
    int i = lo - 1;                       // i 指向「小于等于基准」区域的末尾

    for (int j = lo; j < hi; j++)
    {
        cmp++;
        if (a[j] <= pivot)
        {
            i++;
            (a[i], a[j]) = (a[j], a[i]);
            swaps++;
        }
    }

    (a[i + 1], a[hi]) = (a[hi], a[i + 1]);   // 把基准放到正确位置
    swaps++;
    return i + 1;
}

// ---------- 策略 1：朴素快排（永远取最后一个元素当基准）----------
static void QuickSortNaive(int[] a, int lo, int hi, ref long cmp, ref long swaps)
{
    if (lo >= hi) return;
    int p = Partition(a, lo, hi, ref cmp, ref swaps);
    QuickSortNaive(a, lo, p - 1, ref cmp, ref swaps);
    QuickSortNaive(a, p + 1, hi, ref cmp, ref swaps);
}

分区过程追踪（数组 [3, 8, 1, 9, 2, 7]，基准 = 7）：

返回 $i + 1 = 3$ —— 基准 7 落在下标 3，左边全是小的，右边全是大的 ✓

i 的含义：指向"已确认小于等于基准"区域的最后一个位置。每次遇到符合条件的 a[j]，就把它换到 i+1 的位置，然后 i++。

这样做的效果：所有"小的"被紧凑地堆在左边，而"大的"被自然而然地挤到右边（因为交换时把大的换到了后面）。

复杂度：

• 分区本身：$O(n)$ —— 每个元素看一次
• 总复杂度：$T(n) = T(k) + T(n-k-1) + O(n)$，其中 $k$ 是左半的大小
• 如果每次分区都均匀（$k \approx n/2$）：$T(n) = 2T(n/2) + O(n) = O(n \log n)$
• 如果每次分区都极不均匀（$k = 0$）：$T(n) = T(n-1) + O(n) = O(n^2)$

三、最坏情况：比想象中更容易触发

理论上，"每次分区都极不均匀"听起来是个小概率事件。

但实际上，它有一个极其常见的触发条件：数据已经有序。

实验一：朴素快排（$n = 10{,}000$）

  输入类型     |        比较次数 |       交换次数 |      耗时 | 相对 n*log2(n)
----------------------------------------------------------------------------
  随机         |       163,036 |        61,294 |   1.3 ms |     1.23 倍
  已排序       |    49,995,000 |    25,004,999 |  57.0 ms |   376.25 倍
  完全逆序     |    49,995,000 |    25,004,999 |  57.0 ms |   376.25 倍
  全部相同     |    49,995,000 |    50,004,999 |  57.0 ms |   376.25 倍

看这三行：已排序、完全逆序、全部相同 —— 全都是 49,995,000 次比较，是随机数据的 306 倍，是 $n\log_2 n$ 的 376 倍。

而且 $n$ 只有 10,000，耗时就已经是 57 毫秒了。

为什么会这样？

基准永远取最后一个元素。当数组已经有序时：

[1, 2, 3, 4, 5, 6, 7, 8]      基准 = 8（最后一个）
分区后: [1, 2, 3, 4, 5, 6, 7] [8] []
         ↑ 左边 7 个             ↑就位  ↑ 右边 0 个

每次分区都只切掉一个元素（基准自己），剩下 $n-1$ 个元素继续递归。

递归深度变成 $n$，总比较次数：

$$(n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2} = O(n^2)$$

实测的 49,995,000 ≈ $\frac{10000 \times 9999}{2}$，完全吻合。

实验三验证了这个退化：

           n |     朴素快排比较次数 |            n^2/2 |         倍数
----------------------------------------------------------------
     2,000 |            1,999,000 |        2,000,000 |      1.00 倍
     4,000 |            7,998,000 |        8,000,000 |      1.00 倍
     8,000 |           31,996,000 |       32,000,000 |      1.00 倍

数据量翻倍，比较次数涨约 4 倍 —— 标准的 $O(n^2)$。

注意"全部相同"这一行更危险：它的交换次数是 50,004,999，比已排序还多。

因为 a[j] <= pivot 对所有元素都成立，所以每次都要交换。

"全部相同"在现实中非常常见：比如按状态字段排序，而 90% 的记录状态都是"正常"。

还有一个比"慢"更严重的后果：栈溢出。

递归深度变成 $n$ 意味着要去程 $n$ 层（2.2 节）。$n = 10{,}000$ 时已经接近 1 MB 线程栈的极限（实测崩溃点是 16,074 层）。

$n$ 到几十万时，朴素快排会直接崩溃整个进程 —— 不是变慢，是服务挂掉。

四、两种改进策略

策略 1：随机化基准

static void QuickSortRandom(int[] a, int lo, int hi, ref long cmp, ref long swaps, Random rng)
{
    if (lo >= hi) return;

    int randomIdx = rng.Next(lo, hi + 1);            // 随机挑一个位置
    (a[randomIdx], a[hi]) = (a[hi], a[randomIdx]);   // 换到末尾，复用上面的 Partition

    int p = Partition(a, lo, hi, ref cmp, ref swaps);
    QuickSortRandom(a, lo, p - 1, ref cmp, ref swaps, rng);
    QuickSortRandom(a, p + 1, hi, ref cmp, ref swaps, rng);
}

为什么有效？

因为输入数据的顺序，不再和基准的选择相关。即使数据已经排好序，随机选的基准也大概率落在中间，分区依然均匀。

更重要的是：攻击者无法预测基准在哪。 这就堵死了"构造特殊输入让快排退化"的攻击路径（6.1 节讲的哈希碰撞攻击是同一类问题）。

策略 2：三数取中

// 取 lo、mid、hi 三个位置的中位数，换到 hi 位置
int mid = lo + (hi - lo) / 2;
if (a[mid] < a[lo]) (a[lo], a[mid]) = (a[mid], a[lo]);
if (a[hi] < a[lo]) (a[lo], a[hi]) = (a[hi], a[lo]);
if (a[hi] < a[mid]) (a[mid], a[hi]) = (a[hi], a[mid]);
(a[mid], a[hi]) = (a[hi], a[mid]);      // 把中位数换到末尾

先对 a[lo]、a[mid]、a[hi] 排序，再把中位数换到末尾当基准。

对已经有序的数据，"三个位置的中位数"恰好就是中间那个元素 —— 这是最理想的基准。

实测对比

  输入类型     |            朴素 |       随机化基准 |        三数取中
--------------------------------------------------------------------
  随机         |         163,036 |         156,270 |         131,045
  已排序       |      49,995,000 |         156,487 |         113,631
  完全逆序     |      49,995,000 |         165,639 |         218,585
  全部相同     |      49,995,000 |      49,995,000 |      49,995,000

效果非常明显：

随机化基准把"已排序/逆序"的退化彻底消除了。

三数取中在有序数据上甚至比随机化更好（11.4 万 vs 15.6 万）—— 因为"取中位数"对有序数据是精确命中，而随机化只是"平均意义上不错"。

但两种策略都救不了"全部相同"：

当所有元素都相等时，"基准"取哪个都一样 —— 分区依然会分成"$n-1$ 个元素"和"0 个元素"。随机化只是随机地退化，不是不退化。

真正的解法是三路分区（把数组分成 < pivot、= pivot、> pivot 三段）：

[小于基准的] [等于基准的] [大于基准的]
              ↑ 这一整段已经就位，不用递归！

遇到"全部相同"的数据时，一次分区就能把整段"等于"部分确定下来，直接结束递归。

这就是为什么工业级实现在处理重复元素多的数据时，性能差异可以到几十倍。

本节只演示了两种基准选择策略，三路分区的完整实现留给读者自己尝试（练习 8.2.5）。

五、实际速度：快排 vs 官方实现

实验四（100 万随机数据）：

    随机化快排      :     59.7 ms   （比较 24,271,755 次）
    Array.Sort（.NET）:     47.8 ms   （内省排序）
    结果一致 = True

官方实现快约 25%。 它做了很多我们没做的事：

这就是"内省排序"（Introsort） —— 它会监控递归深度，一旦发现"快排要退化了"，立刻切换到堆排序（保证 $O(n \log n)$）。8.5 节会详细讲。

这个对比说明一个重要的工程事实：

"理解算法原理"和"写出生产级实现"之间，隔着一堆工程细节。

实践建议：排序永远用 Array.Sort / List<T>.Sort()，不要自己写。

本节写快排是为了让你理解它为什么快、什么时候会慢 —— 这样当你在某个库的文档里看到"最坏情况 $O(n^2)$"时，能立刻明白那意味着什么。

六、快速排序 vs 归并排序

为什么快排的实际速度更快？

1. 不需要复制数据。 归并排序每次合并都要把元素复制到临时数组再复制回来，两倍的内存带宽。快排只在原数组上交换。
2. 缓存更友好。 快排的分区是顺序扫描数组，对缓存非常友好。
3. 常数更小。 分区操作比合并操作简单（一个循环 + 交换，vs 三个循环 + 数组复制）。

一句话总结两者：

• 快排：平均更快，但性能依赖输入。加了随机化和内省保护之后可以放心用。
• 归并：慢一点，但永远不变。需要稳定性或可预测性时选它。

.NET 的选择：Array.Sort 用内省排序（快排为主 + 堆排序兜底）—— 追求速度，用工程手段消除最坏情况。但它不稳定。

需要稳定排序时，用 LINQ 的 OrderBy（它是归并类的实现）。

七、练习

练习 8.2.1（手写分区） 数组 [6, 2, 8, 3, 9, 1, 7]，基准取最后一个元素 7。 请手工推演 Lomuto 分区的每一步（列出 $j$、$a[j]$、$i$ 的变化），并给出分区后的数组和基准的最终下标。

练习 8.2.2（推导最坏情况） (a) 什么情况下快排会退化到 $O(n^2)$？给出三种不同的输入类型。 (b) 在最坏情况下，递归深度是多少？ (c) 如果 $n = 100{,}000$，最坏情况的比较次数大约是多少？按每次比较 1 纳秒算，需要多久？

练习 8.2.3（判断） 判断对错并说明理由： (a) 快速排序的最坏情况很少发生，实际中不用管。 (b) 随机化基准能保证快排不退化。 (c) 三数取中比随机化基准更好。

练习 8.2.4（工程判断） 一个服务的接口接收用户上传的数组，然后排序返回。攻击者发现可以构造特殊输入让这个接口变慢 1000 倍，从而拖垮服务。 (a) 攻击者用的是什么输入？ (b) 如果你用 Array.Sort（.NET 的内省排序），还会被攻击吗？为什么？ (c) 除了换排序算法，还有什么防御手段？

练习 8.2.5（挑战·三路分区） 实现三路分区的快速排序：把数组分成 < pivot、= pivot、> pivot 三段，中间那段不再递归。 (a) 写出分区逻辑（提示：需要三个指针）。 (b) 说明为什么它能解决"全部相同"的退化问题。 (c) 用你之前的"全部相同"测试数据验证效果。

八、练习答案

8.2.1

数组 [6, 2, 8, 3, 9, 1, 7]，基准 = a[6] = 7。

基准最终落在下标 4。

验证：左边 [6, 2, 3, 1] 都 $\le 7$ ✓；右边 [8, 9] 都 $> 7$ ✓

8.2.2

(a) 三种会退化的输入：

1. 已经有序的数组（升序）
2. 完全逆序的数组（降序）
3. 所有元素都相同（或大量重复）

共同特征：每次分区都极度不平衡（一边 0 个元素、另一边 $n-1$ 个）。

补充：对于随机化基准的实现，这三种都不再退化。但"全部相同"仍然退化（因为随机选哪个都一样）。

还有一种人为的退化：攻击者知道你的基准选择策略（比如"永远取中间位置"），然后构造出让"中间位置恰好是最大或最小值"的输入。这就是 6.1 节哈希碰撞攻击的排序版本。

(b) 递归深度 = $n$。

每层只减少一个元素，所以要去程 $n$ 层。

(c) 比较次数：

$$\frac{n(n-1)}{2} = \frac{100000 \times 99999}{2} \approx 5 \times 10^9$$

50 亿次比较，按每次 1 纳秒算是 5 秒。

而正常情况（$O(n \log n)$）只需要：

$$10^5 \times 17 = 1.7 \times 10^6 \text{ 次} = 1.7 \text{ 毫秒}$$

差了 3000 倍。 而且 5 秒的计算还会阻塞线程，在高并发下直接拖垮服务。

更糟的是：递归深度 $n = 100{,}000$ 远超栈的极限（实测约 16,074 层），会直接崩溃。所以实际后果不是"慢 5 秒"，而是"进程挂掉"。

8.2.3

• (a) 错，本节实测就是反例。 "已排序的数组"在现实中极其常见：
  • 从数据库查出来的、已经按主键排好的数据
  • 日志文件（本来就是按时间追加的）
  • 用户上传的、已经排好序的名单 >

    朴素快排遇到这些数据会立刻退化到 $O(n^2)$，甚至崩溃。

    而且"不用管"还有个前提：如果输入来自用户，攻击者会主动构造最坏输入（练习 8.2.4）。

• (b) 错。 随机化基准能消除"有序/逆序"的退化，但"全部相同"仍然退化（实测 49,995,000 次比较，和不加随机化一模一样）。

  准确的说法：随机化基准让"退化变得不可预测"，而不是"不会退化"。

  它真正的价值在于防御攻击 —— 攻击者无法预知基准在哪。

• (c) 要看数据。 实测： | 输入 | 随机化基准 | 三数取中 | |---|---|---| | 随机 | 156,270 | 131,045 | | 已排序 | 156,487 | 113,631 | | 完全逆序 | 165,639 | 218,585 | >

  三数取中在"有序/随机"上更好（因为"取中位数"是确定性的优化），但在"完全逆序"上反而更差。

  原因：三数取中在完全逆序时，a[lo]、a[mid]、a[hi] 的中位数是靠近 lo 的那个（因为逆序数组里，下标小的值大）……实际上取到的是最接近 lo 的元素，分区会偏向一边。

  工程实践中常用的方案是"两者结合"：用三数取中，但三个位置随机选。这样既有"取中位数"的确定性优势，又有"不可预测"的防御能力。

8.2.4

(a) 攻击者用的是"已经排好序的数组"或"全部相同的数组"。

• 如果服务的实现是朴素快排（基准取第一个或最后一个）：排序号的数组会让它退化到 $O(n^2)$。
• 如果实现是"取中间元素当基准"：攻击者构造一个"中间位置恰好是最小值"的数组 —— 每次分区后，中间位置的元素都被换到边界，分区规模只减少 1。
• "全部相同"的数组：无论基准怎么选都会退化（除非用三路分区）。

（本节实测：$n = 10{,}000$ 时已经是 376 倍的差距。$n$ 更大时差距会到几千倍。）

(b) 用 Array.Sort 就不会被这样攻击。

因为它是内省排序（Introsort），核心保护机制是：

它会监控递归深度。一旦深度超过 $2 \log_2 n$，就立刻切换到堆排序。

堆排序的最坏情况是 $O(n \log n)$（8.3 节）。所以：

即使攻击者成功构造出让快排退化的输入，算法也会在几百次递归后自动切走 —— 攻击效果被限制在"启动阶段"的那点开销里。

这是"用工程手段兜底"的典型范例：不追求"平均最优"，而是保证"最坏可控"。

(c) 其他防御手段：

1. 限制输入规模。 如果业务上不需要排 100 万条，就直接拒绝。攻击的前提是"输入足够大"，掐掉这个前提最有效。
2. 加超时。 给排序操作设置时间上限，超时就中止并返回错误。这能防止"慢"演变成"拖垮整个服务"。
3. 随机化基准。 让攻击者无法预测（即使没换算法，也能大幅提高攻击难度）。
4. 限流。 对这类重计算接口做速率限制，让攻击者无法发起足够多的请求。
5. 异步/后台处理。 把排序放到后台线程池（有界队列），避免占满主线程。

最根本的一条：

只要输入来自不可信的外部，就必须假设"最坏情况一定会被构造出来"。

这不是悲观，而是安全设计的基本假设。6.1 节的哈希碰撞攻击、7.4 节的下界讨论、以及这里的快排退化，背后都是同一个道理。

8.2.5

(a) 三路分区的实现（荷兰国旗问题）

/// <summary>
/// 三路分区：把 a[lo..hi] 分成三段
///   [lo, lt-1]   < pivot
///   [lt, gt]     == pivot
///   [gt+1, hi]   > pivot
/// </summary>
static void QuickSort3Way(int[] a, int lo, int hi)
{
    if (lo >= hi) return;

    int pivot = a[lo + (hi - lo) / 2];      // 取中间的值为基准（值，不是下标）
    int lt = lo;                            // lt: 「小于区」的下一个空位
    int gt = hi;                            // gt: 「大于区」的最后一个位置
    int i = lo;                             // i:  当前扫描位置

    while (i <= gt)
    {
        if (a[i] < pivot)
        {
            (a[lt], a[i]) = (a[i], a[lt]);
            lt++;
            i++;
        }
        else if (a[i] > pivot)
        {
            (a[i], a[gt]) = (a[gt], a[i]);
            gt--;
            // 注意：这里【不递增 i】—— 换过来的元素还没检查过
        }
        else
        {
            i++;                            // 等于基准，留在中间
        }
    }

    // 现在 [lo, lt-1] < pivot，[lt, gt] == pivot，[gt+1, hi] > pivot
    QuickSort3Way(a, lo, lt - 1);           // 只递归小于段
    QuickSort3Way(a, gt + 1, hi);           // 只递归大于段
    // 中间那段 [lt, gt] 完全不用管了！
}

三个指针的分工：

关键细节：当 a[i] > pivot 时，把 a[i] 和 a[gt] 交换后，不能递增 i —— 因为从后面换过来的那个元素还没被检查过，必须重新判断。

(b) 为什么能解决"全部相同"的退化？

看"全部相同"的情况（所有元素都等于 pivot）：

• 每次循环都走 else 分支（i++）
• lt 和 gt 从头到尾不变
• 扫描结束后：lt = lo，gt = hi
• 整个数组 [lo, hi] 都属于"等于区"
• 递归调用的是 QuickSort3Way(a, lo, lo-1) 和 QuickSort3Way(a, hi+1, hi) —— 两个都是空区间，直接返回！

所以"全部相同"的数据只需要一次分区（$O(n)$）就排完了 —— 从 $O(n^2)$ 降到 $O(n)$。

(c) 验证效果：

三路分区是生产级快排的标配 —— .NET 的 Array.Sort（在检测到大量重复时会启用）、Java 的 Arrays.sort（对基本类型用的就是双轴快排，本质上也是三路思想）。

一个重要提醒：三路分区牺牲了稳定性（交换是长距离的，见 7.2 节），而且实现复杂度明显上升（三个指针的边界很容易写错）。

这正是"为什么不要自己写排序"的又一个例证 —— 这些细节，工业实现都替你处理好了。

九、常见错误

十、本节总结

1. 快速排序 = 分区 + 递归。分区把"小的放左边、大的放右边"，基准一次就位（它的位置就是最终位置）。
2. 分区是 $O(n)$，但总复杂度取决于分区是否均匀：均匀是 $O(n \log n)$，极端不均是 $O(n^2)$。
3. 最坏情况极易触发：已排序、完全逆序、全部相同三种输入都会退化（实测 $n=10{,}000$ 时 49,995,000 次比较 = 376 倍 $n\log n$）。
4. 后果不只是慢，还会崩：递归深度 $n$ 会栈溢出。
5. 随机化基准消除"有序/逆序"退化并防御攻击；三数取中在有序数据上更好但逆序时反而差；两者都救不了"全部相同"。
6. 三路分区是"全部相同"的正解 —— 一次分区就把"等于区"整段确定，$O(n^2) \to O(n)$。
7. 快排 vs 归并：快排平均更快、原地、缓存友好，但依赖输入；归并稳定、可预测，但要 $O(n)$ 额外空间。
8. Array.Sort 是内省排序：用递归深度监控 + 切换到堆排序来彻底杜绝最坏情况。实测比手写快排快 25%。生产环境永远用它。

下一节衔接：本节反复提到"内省排序会在递归太深时切换到堆排序"。堆排序究竟是什么？它为什么能保证 $O(n \log n)$？而且它还有一个快排和归并都没有的优点 —— 同时做到 $O(n \log n)$ 和 $O(1)$ 额外空间。下一节讲堆排序。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "8.2",
  "title": "快速排序：平均最快，最坏要防",
  "covered": [
    "分区的直觉（小的放左边、大的放右边、基准一次就位）",
    "Lomuto 分区完整实现与逐步追踪",
    "T(n)=T(k)+T(n-k-1)+O(n) 的复杂度分析",
    "三种退化输入实测（已排序/完全逆序/全部相同，均 376 倍）",
    "退化的原因（每次只切掉基准自己，深度变 n）与栈溢出风险",
    "随机化基准与三数取中的实现与对比实测",
    "「随机化只让退化不可预测，不消除退化」",
    "三路分区的思路与「全部相同」的解决",
    "与 Array.Sort（内省排序）的实测对比（59.7ms vs 47.8ms）",
    "快排 vs 归并的完整对比",
    "排序退化的攻击面与防御手段"
  ],
  "unresolved": [
    "堆排序留到 8.3",
    "内省排序的完整实现留到 8.5",
    "哈希碰撞攻击在 6.1 已讲，此处呼应"
  ],
  "canonical_terms": {
    "快速排序": "分区后递归，基准一次就位，原地排序",
    "基准": "分区时用来比较的参照元素",
    "分区": "把数组整理成小于基准在左、大于基准在右",
    "最坏情况退化": "分区极度不平衡导致复杂度降到 O(n^2)"
  },
  "symbols_units": {},
  "assumptions": [
    "读者已掌握 8.1 的归并排序与 2.4 的分治",
    "读者理解 2.2 节的栈溢出"
  ],
  "word_count_actual": 3600,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch08/Sec82/",
    "四种输入 × 三种策略的比较次数、退化倍数（376 倍）、Array.Sort 对比均为实测",
    "练习 8.2.1 的分区推演已手工验算（基准落在下标 4）",
    "术语写法与 glossary.md 一致"
  ],
  "next": "8.3 堆与堆排序"
}