Lesson 41: 快速排序

练习任务

难度：中-难【重点】

实现快速排序，包含两个核心函数：

partition(arr, lo, hi) — Lomuto 分区：以 arr[hi] 为 pivot，重排数组使 pivot 归位，返回 pivot 索引
quicksort(arr, lo, hi) — 递归快排：分区后对左右子数组递归

int partition(int arr[], int lo, int hi);
void quicksort(int arr[], int lo, int hi);

swap 函数已提供。验证用例：

输入 "5 3 8 1 4 2\n" → 1 2 3 4 5 8
输入 "9 1 5 3 7\n"   → 1 3 5 7 9

快速排序是工程中最常用的原地排序算法，也是 C 标准库 qsort 的底层基础。Tony Hoare 于 1960 年发明它时年仅 26 岁，2011 年获颁 IEEE 冯·诺依曼奖。理解快排的分治思想与分区操作，是掌握算法设计与分析的关键一步。

提示：快排与归并排序同为分治算法，但有一个本质区别——归并排序是"先递归，后合并"（需要额外空间），快排是"先划分，后递归"（原地完成，无需合并）。理解这一点，你就抓住了快排的核心设计思想。

核心知识点

分治三步骤：划分(partition)→递归左右→无需合并。与归并排序"先递归再合并"形成对比，快排是原地排序的核心优势
Lomuto 分区：i = lo - 1 作为 ≤pivot 区的右边界，j 从 lo 扫描到 hi-1，遇到 ≤ pivot 时 i++ 并交换，最后 swap(arr[i+1], arr[hi]) 使 pivot 归位
Pivot 落最终位不变式：分区完成后，pivot 处于最终排序位置——左侧全 ≤ pivot，右侧全 ≥ pivot。后续递归永远不会再触碰该位置
有序输入 + 末位 pivot → 最坏 O(n²)：每次递归只减少 1 个元素，递归树退化为单链，总比较次数 ≈ n(n-1)/2
随机化 pivot / 三数取中 → 期望 O(n log n)：通过打乱 pivot 选择消除最坏情况，使分区在期望下近乎平衡
Lomuto vs Hoare 划分：pivot 选择位置（hi vs lo）、交换次数（较多 vs 较少）、返回值语义（pivot 位置 vs 分界点）全方位对比
快排 vs 归并 vs 堆排：三者在稳定性、原地性、空间复杂度、缓存局部性上的差异——快排常数小、缓存友好、原地，是"实际最快"
三路划分（荷兰国旗问题）：处理大量重复元素时，将数组分成 < pivot / == pivot / > pivot 三段，避免冗余比较
Introsort：快排 + 堆排混合策略，递归深度超过 2log₂n 时切换堆排，兼顾平均性能和最坏保证。std::sort 和 glibc qsort 的内核

代码框架

41_quick_sort.c

/* 41_quick_sort.c — 快速排序
 *
 * 任务：实现快速排序
 *       1. partition(arr, lo, hi) — Lomuto 分区
 *          选 arr[hi] 为 pivot，扫描 [lo, hi) 区间，小的放左边
 *          返回 pivot 最终位置
 *       2. quicksort(arr, lo, hi) — 递归快排
 *          分区 → 递归排左半 → 递归排右半
 *
 * 知识点：分治、Lomuto 分区、pivot 选择、原地排序
 *
 * 验证：
 *   stdin: "5 3 8 1 4 2\n" → 1 2 3 4 5 8
 *   stdin: "9 1 5 3 7\n"   → 1 3 5 7 9
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

/* Lomuto 分区：
 * - 选 arr[hi] 作为 pivot
 * - i 指向"小于 pivot 的区域"的最后一个位置
 * - j 扫描 [lo, hi)，遇到 ≤ pivot 的元素就交换到左边
 * - 最后把 pivot 放到正确位置 (i+1) */
int partition(int arr[], int lo, int hi) {
    // 在这里实现: 选 pivot = arr[hi]; i = lo - 1
    // for j = lo; j < hi; j++
    //   如果 arr[j] <= pivot: i++; swap(&arr[i], &arr[j])
    // 最后: swap(&arr[i+1], &arr[hi]); return i+1;
}

/* 递归快排 */
void quicksort(int arr[], int lo, int hi) {
    // 在这里实现: 终止条件 lo >= hi → return
    // 分区: p = partition(arr, lo, hi)
    // 递归左: quicksort(arr, lo, p-1)
    // 递归右: quicksort(arr, p+1, hi)
}

int main(void) {
    char line[1024];
    fgets(line, sizeof(line), stdin);

    int arr[1024], n = 0;
    char *tok = strtok(line, " \n");
    while (tok) {
        arr[n++] = atoi(tok);
        tok = strtok(NULL, " \n");
    }

    quicksort(arr, 0, n - 1);

    for (int i = 0; i < n; i++) {
        if (i > 0) printf(" ");
        printf("%d", arr[i]);
    }
    printf("\n");
    return 0;
}

阅读骨架后，尝试自己填充 // 在这里... 标记的部分。核心挑战在于：i 的初始值为什么是 lo - 1 而不是 lo？j 的扫描范围为什么是 lo 到 hi-1（不含 pivot）？pivot 归位为什么是 swap(arr[i+1], arr[hi]) 而不是 swap(arr[i], arr[hi])？

TIP

先不要往下翻看参考解答。尝试在纸上画出 i 和 j 的运动轨迹——i 永远指向 ≤pivot 区域的最后一个元素，j 是探索指针。当 j 发现一个 ≤pivot 的元素时，"≤区"向右扩展一位，把该元素交换进去。最后 pivot 自己还没有进 ≤区，所以放在 i+1 处。

深度讲解

4.1 分治：划分 → 递归 → 无需合并

分治（Divide and Conquer）是将问题分解为子问题、递归求解、再合并的通用策略。快排和归并排序都遵循分治框架，但对三步的映射完全不同：

        归并排序（Merge Sort）                快速排序（Quick Sort）
        ════════════════════════              ══════════════════════

Divide:  对半分（无实际工作）               Partition：将数组按 pivot 重排
                                        [≤pivot] [pivot] [≥pivot]
               │                                      │
               ▼                                      ▼
Conquer:  递归排序左半                           递归排序左半
          递归排序右半                           递归排序右半
               │                                      │
               ▼                                      ▼
Combine:  Merge 合并两个有序子数组        ← 无需合并！pivot 已归位，左右独立排序后整体有序
          需要 O(n) 额外空间              原地完成，无额外数组

关键洞察：归并排序的工作量集中在"合并"阶段（需要遍历两个子数组，复制到临时空间），而快排的工作量集中在"划分"阶段（重排数组使 pivot 归位）。因为划分操作直接在原地完成，且 pivot 被放到最终正确位置后永不再移动，所以递归完成后无需合并。

这一设计差异带来了实际性能的重大区别：

	归并排序	快速排序
主要工作量	合并阶段	划分阶段
是否原地	否（需临时数组）	是（原地分区）
空间复杂度	O(n)	O(log n) （仅递归栈）
缓存局部性	一般（合并时跨区域读写）	极好（顺序扫描数组）

NOTE

快排的"无需合并"只有在前一个条件——pivot 被放到最终正确位置——成立时才成立。这正是 Lomuto 分区（及任何正确分区）必须保证的不变式，也是下一节的核心。

4.2 Lomuto 分区：全程逐轮跟踪

Lomuto 分区以 arr[hi] 为 pivot，维护两个指针：

i：≤pivot 区域的右边界（初始 lo - 1，表示 ≤区为空）
j：扫描指针，从 lo 遍历到 hi - 1（不含 pivot 自身）

算法流程：

1. pivot = arr[hi]
2. i = lo - 1
3. for j = lo; j < hi; j++:
     if arr[j] <= pivot:
        i = i + 1
        swap(arr[i], arr[j])
4. swap(arr[i + 1], arr[hi])   // pivot 归位
5. return i + 1                // 返回 pivot 的最终位置

以 [5, 3, 8, 1, 4, 2] 为例，pivot = arr[hi] = 2，全程逐轮跟踪：

═══════════════════════════════════════════════════════════════════
初始状态:
  arr = [5, 3, 8, 1, 4, 2]
         ↑              ↑
         j              pivot
  pivot = 2,  i = -1 (lo - 1 = 0 - 1)

说明: j 从索引 0 开始扫描，i 指向 ≤2 区的末尾（当前为空，所以是 -1）
═══════════════════════════════════════════════════════════════════

j = 0:  arr[0] = 5
        5 > 2 → 不满足 ≤ pivot 条件
        不做任何操作，i 保持 -1
        arr = [5, 3, 8, 1, 4, 2]   (不变)
              ↑                    i=-1
              j

j = 1:  arr[1] = 3
        3 > 2 → 不满足条件
        arr = [5, 3, 8, 1, 4, 2]   (不变)
                 ↑                 i=-1
                 j

j = 2:  arr[2] = 8
        8 > 2 → 不满足条件
        arr = [5, 3, 8, 1, 4, 2]   (不变)
                    ↑              i=-1
                    j

j = 3:  arr[3] = 1
        1 ≤ 2 → 满足条件！
        (1) i = i + 1 = 0         → i 从 -1 变成 0
        (2) swap(arr[0], arr[3])   → 5 和 1 交换位置
        arr = [1, 3, 8, 5, 4, 2]
               ↑        ↑
               i        j
        解读: ≤2 区现在包含 arr[0]=1，i=0 标记了它的右边界

j = 4:  arr[4] = 4
        4 > 2 → 不满足条件
        arr = [1, 3, 8, 5, 4, 2]
               ↑           ↑     i=0
               i           j

═══════════════════════════════════════════════════════════════════
扫描完成 (j 遍历了 lo..hi-1 即 0..4)
═══════════════════════════════════════════════════════════════════

pivot 归位:
  swap(arr[i + 1], arr[hi])
  = swap(arr[0 + 1], arr[5])
  = swap(arr[1], arr[5])
  → 交换 arr[1]=3 和 arr[5]=2

  arr = [1, 2, 8, 5, 4, 3]
         ←≤2→ ↑ ←──≥2──→
         i=0  p=1  余下

  return i + 1 = 1   (pivot 的最终位置)

结果验证:
  arr[0..0] = [1]    全部 ≤ 2 ✓
  arr[1]     = 2     pivot 归位 ✓
  arr[2..5] = [8,5,4,3]  全部 ≥ 2 ✓

三个变量的含义总结：

i:   ≤pivot 区域的右边界（闭区间 [0, i] 全 ≤ pivot）
     初始 lo-1 = 空区间
     每次 arr[j] ≤ pivot 时 i 右移一位

j:   扫描指针（闭区间 [i+1, j-1] 是已扫描的 >pivot 区域）
     每次迭代 j 右移一位

pivot: 基准值 arr[hi]，本身不在 j 的扫描范围内

IMPORTANT

为什么 i 初始是 lo - 1 而不是 lo？ 因为 ≤pivot 区初始为空，用 i = lo - 1 表示"右边界在左边界之前"。如果初始设为 lo，则第一个 ≤pivot 元素被交换时 swap(arr[lo], arr[j]) 会丢掉 arr[lo]。

4.3 Pivot 落在最终位置：不变式的力量

Lomuto 分区完成后，以下不变式同时成立：

arr[lo  .. p-1]  ≤  arr[p]  ≤  arr[p+1 .. hi]
  ← 全部 ≤pivot →   pivot     ← 全部 ≥pivot →

这个不变式不是巧合，而是算法每一步都精心维护的结果。证明思路：

循环不变式（for 循环的每次迭代前）：

arr[lo..i] 全部 ≤ pivot
arr[i+1..j-1] 全部 > pivot
arr[j..hi-1] 尚未扫描

初始（i = lo - 1, j = lo）：三个区间均为空，平凡成立。

保持（每次迭代）：

若 arr[j] ≤ pivot：i++ 后 swap(arr[i], arr[j])，即两个边界都向右移动，≤区扩大一位，arr[j]（原 > 区边界元素）被交换到 > 区首部。不变式保持。
若 arr[j] > pivot：仅 j++，> 区自然扩大一位。不变式保持。

终止（j = hi）：

arr[lo..i] 全部 ≤ pivot
arr[i+1..hi-1] 全部 > pivot
arr[hi] 是 pivot 自己

最后 swap(arr[i+1], arr[hi]) 将 pivot 插入 ≤区和 >区之间，恰好满足最终不变式。

NOTE

不变式的精妙之处在于：pivot 一旦归位，后续递归永远不会再触碰它。左递归处理 lo..p-1，右递归处理 p+1..hi——pivot 索引 p 被完美跳过。这就是为什么快排可以"原地"工作：每一轮都确定了一个元素的最终位置，总共 n 轮即可完成整数组的排序。

4.4 有序输入 + 末位 pivot → 最坏 O(n²)：逐轮跟踪证明

为什么最坏情况是 O(n²)？ 如果每次选取的 pivot 都是当前子数组的最值（最小或最大），则分区极不平衡——一边为空，另一边只减少 1 个元素。

典型触发场景：已排序数组 [1, 2, 3, 4, 5]，始终选 arr[hi]（最后一个元素）为 pivot。

═══════════════════════════════════════════════════════════════════
第 1 轮: quicksort(arr, 0, 4)
  arr = [1, 2, 3, 4, 5], pivot = arr[4] = 5
  ═══════════════════════════════════════
  j=0: 1 ≤ 5 → i++, swap(arr[0], arr[0])   (自交换，可优化跳过)
  j=1: 2 ≤ 5 → i++, swap(arr[1], arr[1])
  j=2: 3 ≤ 5 → i++, swap(arr[2], arr[2])
  j=3: 4 ≤ 5 → i++, swap(arr[3], arr[3])
  ═══════════════════════════════════════
  迭代次数: 4 次 (j 从 0 到 3)
  swap(arr[4], arr[4]) → 自交换，p=4
  结果: [1, 2, 3, 4] [5]    ← 右子数组空，左子数组仅减少 1
        ← left 4个 →  ↑pivot

第 2 轮: quicksort(arr, 0, 3)
  arr = [1, 2, 3, 4], pivot = arr[3] = 4
  j=0,1,2: 全部 ≤4，各交换一次
  迭代次数: 3 次
  p=3, 结果: [1, 2, 3] [4]

第 3 轮: quicksort(arr, 0, 2)
  arr = [1, 2, 3], pivot = arr[2] = 3
  j=0,1: 全部 ≤3
  迭代次数: 2 次
  p=2, 结果: [1, 2] [3]

第 4 轮: quicksort(arr, 0, 1)
  arr = [1, 2], pivot = arr[1] = 2
  j=0: 1 ≤ 2
  迭代次数: 1 次
  p=1, 结果: [1] [2]

终止: quicksort(arr, 0, 0) → lo ≥ hi，返回
═══════════════════════════════════════════════════════════════════

总迭代次数 (即比较次数): 4 + 3 + 2 + 1 = 10
通项公式: (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n²)

递归树的可视化：

正常快排（平衡分区）:              最坏快排（退化分区）:
        [5,3,8,1,4,2]                   [1,2,3,4,5]
       /              \                 /            \
  [1,2]               [8,5,4]       [1,2,3,4]       [ ]
  /    \              /     \       /        \
[1]   [2]          [4,5]   [8]  [1,2,3]     [ ]
                   /   \        /      \
                 [4]   [5]   [1,2]    [ ]
                             /   \
                           [1]   [2]

深度: O(log n)                    深度: O(n)
每层工作量: O(n)                   每层工作量: O(n - depth)
总计: O(n log n)                   总计: O(n²)

树形: 接近完全二叉树               树形: 退化为单链 (链表)

WARNING

在真实工程中，已排序数据是最坏输入的情况非常常见（例如从数据库读取已按时间排序的记录）。如果始终选末尾元素为 pivot，每次快速排序都会退化到 O(n²)。对于 n = 10⁵，n² = 10¹⁰ 与 n log₂n ≈ 1.7×10⁶ 差了近 6000 倍——这足以让一个"正常工作"的程序在面对已排序输入时直接卡死。

4.5 随机化 pivot 与三数取中：修复最坏情况

4.5.1 随机化 pivot

在分区前将 pivot 与随机位置交换，再正常执行 Lomuto 分区：

// 随机化版本
#include <stdlib.h>
#include <time.h>

int randomized_partition(int arr[], int lo, int hi) {
    int rand_idx = lo + rand() % (hi - lo + 1);
    swap(&arr[rand_idx], &arr[hi]);  // pivot 换到末尾
    return partition(arr, lo, hi);   // 照常分区
}

概率分析：随机化后，pivot 会等概率地落在排序后任意位置。则：

pivot 落在中间 50% 区域（即分区比 ≥ 1:3）的概率为 1/2
即便最坏 pivot 选择发生，每次二选一，连续 k 次选到最坏的概率为 (1/2)^k，指数衰减

因此期望时间复杂度为 O(n log n)。严格的期望分析与递归树展开有关——即使存在低概率的坏分区，它们在期望值中被更多的好分区平均掉了。

TIP

调用 srand(time(NULL)) 初始化随机种子。但如果需要可复现的调试行为，用固定种子 srand(42)——这样每次运行时 pivot 选择序列相同。

4.5.2 三数取中（Median of Three）

取 arr[lo]、arr[mid]、arr[hi] 三者的中位数作为 pivot：

int median_of_three(int arr[], int lo, int hi) {
    int mid = lo + (hi - lo) / 2;
    // 三数排序: 将中位数放到 arr[hi]
    if (arr[lo] > arr[mid]) swap(&arr[lo], &arr[mid]);
    if (arr[lo] > arr[hi])  swap(&arr[lo], &arr[hi]);
    if (arr[mid] > arr[hi]) swap(&arr[mid], &arr[hi]);
    // 此时 arr[mid] 是三个数的中位数
    swap(&arr[mid], &arr[hi]);  // 将中位数作为 pivot 放到末尾
    return partition(arr, lo, hi);
}

三数取中示意:

  arr[lo]          arr[mid]         arr[hi]
    5                2                8
    │                │                │
    └──────────┬─────┘                │
               ▼                      │
         (5 > 2 → swap)              │
               │                      │
               ▼                      ▼
     arr[2]=mid → arr[5]=lo    arr[8]=hi  (不变)
     
  三数: lo=5, mid=2, hi=8 → 中位数 = 5 → 选为 pivot

结果分析：

已排序数组 [1,2,3,4,5]：三数取 lo=1, mid=3, hi=5 的中位数 3，分区为 [1,2] [3] [4,5]，完美二分 ✓
逆序数组 [5,4,3,2,1]：三数取 5,3,1 的中位数 3，同样完成二分 ✓
三数取中的开销是常数级（3 次比较 + 若干 swap），而避免最坏 O(n²) 的收益是渐近级差异

NOTE

三数取中同时解决了已排序输入和逆序输入两种最坏情况，且不带随机性（结果可复现），因此在工业实现中（如 std::sort）被广泛使用。相比之下，随机化 pivot 提供了对所有输入模式的期望保障，但引入了非确定性。

4.6 Lomuto vs Hoare 划分：完整对比

Tony Hoare 在 1960 年提出的原始快排使用了一种不同的分区方案（后来以他命名）。两种方案的核心差异在于扫描方向和 pivot 位置：

Hoare 分区伪代码

int hoare_partition(int arr[], int lo, int hi) {
    int pivot = arr[lo];           // ← 选 arr[lo] 为 pivot
    int i = lo - 1, j = hi + 1;
    while (1) {
        do { i++; } while (arr[i] < pivot);   // 左指针找 ≥pivot
        do { j--; } while (arr[j] > pivot);   // 右指针找 ≤pivot
        if (i >= j) return j;                  // 返回分界点
        swap(&arr[i], &arr[j]);                // 交换错位对
    }
}

Hoare 分区执行示意 (pivot = arr[lo] = 5):

  arr = [5, 3, 8, 1, 4, 2]
         ↑              ↑
        i=lo          j=hi

  第1轮: i找到 5≥5, j找到 2≤5 → swap(5,2)
         [2, 3, 8, 1, 4, 5]

  第2轮: i找到 8≥5, j找到 4≤5 → swap(8,4)
         [2, 3, 4, 1, 8, 5]

  第3轮: i找到 8≥5, j找到 1≤5 → i≥j, 返回 j
         结果: lo..j 全 ≤5, j+1..hi 全 ≥5

  return j (不是 pivot 位置！pivot=5 可能在左侧任何位置)

完整对比表

维度	Lomuto 分区	Hoare 分区
pivot 选择	`arr[hi]`（末尾）	`arr[lo]`（开头，或中间）
扫描方向	单向扫描（从左到右）	双向扫描（两端向中间）
指针数量	2 个（`i`, `j`）	2 个（`i` 从左，`j` 从右）
交换次数	较多（每个 ≤pivot 的元素都交换）	较少（仅交换错位对）
返回值语义	pivot 的最终位置	分界点 `j`，保证 `lo..j` ≤ pivot ≤ `j+1..hi`
递归调用	`quicksort(lo, p-1)`; `quicksort(p+1, hi)`	`quicksort(lo, j)`; `quicksort(j+1, hi)`
是否有元素留在原地	pivot 确定归位	pivot 不一定归位
重复元素处理	`≤` 判断使相等元素归左侧	相等元素可能分布两侧
教学友好度	直观清晰，不变式容易理解	边界条件较多，指针交叉逻辑需小心
性能（常数因子）	偏慢（更多 swap）	偏快（更少 swap，约 3 倍）

NOTE

核心差异：Lomuto 返回 pivot 的最终位置——递归时跳过 p。Hoare 返回 分界点 j——递归时左区间包含 j（因为 pivot 可能还在左边）。这导致递归调用方式不同：Lomuto 用 p-1 / p+1；Hoare 用 j / j+1。

为什么本题选 Lomuto 而非 Hoare？

教学价值：Lomuto 的循环不变式直观（≤区边界清晰），返回值语义明确（pivot 的位置），适合第一次理解分区操作
错误风险低：Hoare 分区的指针交叉和边界条件容易出错（如 do-while 越界需要哨兵），不适合作为入门方案
后续可扩展：理解 Lomuto 的 ≤区边界后，三路划分（荷兰国旗）的 lt/gt 双边界设计自然延伸

4.7 快排 vs 归并 vs 堆排：三大 O(n log n) 排序全方位对比

                        快排            归并            堆排
                        (Quick Sort)    (Merge Sort)    (Heap Sort)
                        ════════════    ═══════════    ═══════════
平均时间复杂度          O(n log n)      O(n log n)      O(n log n)
最坏时间复杂度          O(n²)           O(n log n)      O(n log n)
最好时间复杂度          O(n log n)      O(n log n)      O(n log n)

额外空间                O(log n)        O(n)            O(1)
                        （递归栈）      （临时数组）    （原地）

稳定性                  ❌ 不稳定       ✅ 稳定         ❌ 不稳定
（相等元素相对顺序）    （分区破坏顺序）（合并保持顺序）（堆调整破坏顺序）

原地排序                ✅ 是           ❌ 否           ✅ 是

缓存局部性              ✅ 极好         🟡 一般         ❌ 差
（连续内存访问模式）    （顺序扫描）    （跨区域归并）  （跳跃式父子访问）

常数因子                最小 (~1.4)     中等 (~2.0)     较大 (~3.0)
（log n 前的系数）

递归 / 迭代             递归            递归            迭代

适用场景                通用排序首选    外排序、链表    优先队列、Top-K
                        稳定排序需求    嵌入式（空间有限）

缓存局部性详解

这也许是三者在实践中最被忽略但最重要的差异：

快排的扫描模式（对 L1/L2 缓存极其友好）:
  顺序扫描 [lo..hi]，相邻元素地址连续:
  ┌─┬─┬─┬─┬─┬─┬─┬─┐
  │5│3│8│1│4│2│ │ │  → cache line 一次性加载，后续命中率极高
  └─┴─┴─┴─┴─┴─┴─┴─┘

归并排序的合并模式（需要来回访问两个数组）:
  读:  [1,3,5]    写: 临时数组
  读:  [2,4,6]    写: 临时数组
  跨区域跳跃，cache miss 较多

堆排序的父子访问模式（索引跳跃 n → n/2）:
  parent(i) = (i-1)/2
  children(i) = 2i+1, 2i+2
  每次 sift-down 跳跃访问，cache miss 最多

IMPORTANT

快排为什么是"实际最快"？ 不是因为渐近复杂度更低（三者都是 O(n log n)），而是因为常数因子最小（每个元素平均参与约 1.4 次比较），并且顺序扫描模式使 CPU 缓存命中率极高。在现代 CPU 上，主存访问比缓存访问慢约 100 倍——缓存局部性的优势在 n 较大时可转化为数倍甚至十数倍的性能差距。

4.8 三路划分：荷兰国旗问题

4.8.1 需求场景

当数组中存在大量重复元素时，标准的 Lomuto/Hoare 二分法会做无用功——相等的元素被反复划分和递归。例如排序全是 0 和 1 的数组：

标准快排: [0,1,0,1,0,1] → partition → [0,0,0,1,1,1]
各层仍然处理含 1 的中间区域，冗余比较很多

三路快排: 将数组一次性分为 [0,0,0] [ ] [1,1,1]
         pivot=1 时 <1 区为全0，=1 区为全1，>1 区为空
         一轮完成！无需递归

荷兰国旗问题*Dijkstra 1976）：将一个红白蓝三色旗重新排列为单色块，恰好对应将数组分为 < pivot、== pivot、> pivot 三段。

4.8.2 算法

维护三个指针：

  lo                             hi
   ↓                              ↓
  [  ? ? ? ? ? ? ? ? ? ? ? ?  ]
   ↑        ↑           ↑
  lt        i           gt

  区间含义:
    [lo,   lt-1]  →  < pivot  (左侧区)
    [lt,   i-1 ]  →  == pivot (中间区)
    [i,    gt  ]  →  未处理区
    [gt+1, hi  ]  →  > pivot  (右侧区)

void three_way_qsort(int arr[], int lo, int hi) {
    if (lo >= hi) return;

    // 三数取中选择 pivot
    int mid = lo + (hi - lo) / 2;
    if (arr[lo] > arr[mid]) swap(&arr[lo], &arr[mid]);
    if (arr[lo] > arr[hi])  swap(&arr[lo], &arr[hi]);
    if (arr[mid] > arr[hi]) swap(&arr[mid], &arr[hi]);
    int pivot = arr[mid];

    int lt = lo, i = lo, gt = hi;
    while (i <= gt) {
        if (arr[i] < pivot) {
            swap(&arr[lt], &arr[i]);
            lt++; i++;               // <区右扩，扫描指针前进
        } else if (arr[i] > pivot) {
            swap(&arr[i], &arr[gt]);
            gt--;                    // >区右扩，扫描指针不动（换来的元素未检查）
        } else {
            i++;                     // ==区自然扩大
        }
    }
    // 分区完成: [lo..lt-1] < pivot, [lt..gt] == pivot, [gt+1..hi] > pivot

    three_way_qsort(arr, lo, lt - 1);   // 只递归 < 和 > 两段
    three_way_qsort(arr, gt + 1, hi);   // == 段已就位，跳过
}

4.8.3 逐步演示

以 [4, 2, 4, 2, 4, 1] 为例，pivot = 4：

初始:  lt=0  i=0  gt=5
       [4, 2, 4, 2, 4, 1]
       ↑                 ↑
      lt,i              gt

i=0: arr[0]=4 == pivot → i++
     [4, 2, 4, 2, 4, 1]   lt=0, i=1, gt=5
      ↑  ↑
     lt  i

i=1: arr[1]=2 < pivot → swap(lt,i), lt++, i++
     [2, 4, 4, 2, 4, 1]   lt=1, i=2, gt=5
         ↑  ↑
        lt  i

i=2: arr[2]=4 == pivot → i++
     [2, 4, 4, 2, 4, 1]   lt=1, i=3, gt=5
         ↑     ↑
        lt     i

i=3: arr[3]=2 < pivot → swap(lt,i), lt++, i++
     [2, 2, 4, 4, 4, 1]   lt=2, i=4, gt=5
            ↑     ↑
           lt     i

i=4: arr[4]=4 == pivot → i++
     [2, 2, 4, 4, 4, 1]   lt=2, i=5, gt=5
            ↑        ↑
           lt       i,gt

i=5: arr[5]=1 < pivot → swap(lt,i), lt++, i++
     [2, 2, 1, 4, 4, 4]   lt=3, i=6, gt=5
               ↑  ↑     ↑
              lt  gt    i

i=6 > gt → 退出循环

结果:
  < 4:  [2, 2, 1]    (lo..lt-1 = 0..2)
  == 4: [4, 4, 4]    (lt..gt = 3..5)  ← 已就位，跳过递归
  > 4:  [ ]           (gt+1..hi = 6..5, 空)

TIP

关键技巧：遇到 arr[i] > pivot 时，swap(arr[i], arr[gt]) 后 i 不动——因为从 gt 换来的元素尚未检查。遇到 arr[i] < pivot 时，swap(arr[lt], arr[i]) 后 i++——因为从 lt 换来的元素已被 i 检查过（就是 ==pivot 区的第一个元素，在 i 扫描到它之前已经被确认等于 pivot）。

三路划分的优势：

大量重复元素时远快于标准快排：时间复杂度从 O(n²/D) 降到 O(n)（其中 D 是不同值的数量）
Java 的 Arrays.sort() 对基本类型使用 Dual-Pivot Quicksort（三路划分的扩展）
对仅有少量不同值的数组接近线性时间

4.9 Introsort：快排 + 堆排的混合策略

4.9.1 动机

纯快排的问题：最坏 O(n²) 总存在理论可能。纯堆排的问题：常数因子大，缓存不友好，平均比快排慢 2-3 倍。

能不能鱼与熊掌兼得？ —— David Musser 在 1997 年提出 Introsort（Introspective Sort）：大多数情况用快排（取其速度优势），递归过深时切换堆排（取其最坏保证）。

4.9.2 深度阈值的计算

为什么阈值是 2·log₂ n？

平衡快排的递归深度:   ~ log₂ n
                    （每次分区接近二分）

退化快排的递归深度:   ~ n
                    （每次分区只减少 1 个元素）

阈值设为 2·log₂ n 的理由:
  - 如果深度 > 2·log₂ n，分区严重不平衡
  - 继续快排可能进入 O(n²) 区域
  - 此时切换到堆排，用 O(n log n) 完成剩余工作
  - 2 倍系数给"正常波动"留出余量，不因偶然稍深的分区就误切换

递归深度示意:

深度 0:  ┌──────────────────┐
         │     n elements    │
深度 1:  ┌──────┐  ┌────┬──────┐
         │ n/2  │  │   n/2   │     正常: 平衡分区
深度 2:  ┌──┐┌──┐┌──┐┌──────┐
         │  ││  ││  ││      │
         ...
深度 log₂n:  叶子层 → 排序完成

如果某分支深度 > 2·log₂ n → 检测到退化，切换堆排

4.9.3 Introsort 伪代码

#define DEPTH_LIMIT(n) (2 * ((int)(log2(n))))

void introsort(int arr[], int lo, int hi, int depth_limit) {
    if (lo >= hi) return;

    // 小数组直接用插入排序（常数因子更优）
    if (hi - lo < 16) {
        insertion_sort(arr, lo, hi);
        return;
    }

    // 递归过深 → 切换堆排，保证最坏 O(n log n)
    if (depth_limit == 0) {
        heapsort_range(arr, lo, hi);
        return;
    }

    // 正常快排：三数取中 + Hoare 分区
    int p = hoare_partition(arr, lo, hi);
    introsort(arr, lo, p,     depth_limit - 1);
    introsort(arr, p + 1, hi, depth_limit - 1);
}

// 入口
void sort(int arr[], int n) {
    introsort(arr, 0, n - 1, DEPTH_LIMIT(n));
}

IMPORTANT

Introsort 是真实世界的标准答案：

std::sort（C++ 标准库）：introsort 核心 + 插入排序优化小数组
glibc qsort（C 标准库）：introsort 核心（自 glibc 2.38 起）
.NET Array.Sort：introsort 变体
Go sort.Sort：pdqsort（pattern-defeating quicksort，introsort 的进化版）

三层优化总结：

层次	策略	解决的问题
第 1 层	三数取中 pivot	防御已排序 / 逆序输入
第 2 层	深度检测 + 堆排兜底	防御任意模式的最坏输入
第 3 层	小数组切换插入排序	利用插入排序对短数组的常数优势（通常 < 16 个元素）

参考解答

参考解答（Lomuto 快排）

solution_41_quick_sort.c

/* solution_41_quick_sort.c — 快速排序参考解答
 *
 * 实现: Lomuto 分区 + 递归快排
 * 时间复杂度: 平均 O(n log n), 最坏 O(n²)
 * 空间复杂度: O(log n) 递归栈
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

/* Lomuto 分区：选 arr[hi] 为 pivot，将所有 ≤pivot 的元素移动到左边
 * 返回值：pivot 的最终位置 */
int partition(int arr[], int lo, int hi) {
    int pivot = arr[hi];
    int i = lo - 1;                     /* ≤区右边界，初始为空 */

    for (int j = lo; j < hi; j++) {     /* j 扫描 lo..hi-1 */
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);     /* 将小元素收入 ≤区 */
        }
    }
    swap(&arr[i + 1], &arr[hi]);        /* pivot 归位到 ≤区之后 */
    return i + 1;                       /* pivot 的最终位置 */
}

/* 递归快排 */
void quicksort(int arr[], int lo, int hi) {
    if (lo >= hi) return;               /* 终止条件：空或单元素 */
    int p = partition(arr, lo, hi);     /* 分区，pivot 归位 */
    quicksort(arr, lo, p - 1);          /* 递归排序左半 */
    quicksort(arr, p + 1, hi);          /* 递归排序右半 */
}

int main(void) {
    char line[1024];
    fgets(line, sizeof(line), stdin);

    int arr[1024], n = 0;
    char *tok = strtok(line, " \n");
    while (tok) {
        arr[n++] = atoi(tok);
        tok = strtok(NULL, " \n");
    }

    quicksort(arr, 0, n - 1);

    for (int i = 0; i < n; i++) {
        if (i > 0) printf(" ");
        printf("%d", arr[i]);
    }
    printf("\n");
    return 0;
}

参考解答（随机化快排 + 尾递归优化）

solution_41_quick_sort_optimized.c

/* solution_41_quick_sort_optimized.c — 快速排序优化版
 *
 * 优化:
 *   1. 随机化 pivot 避免最坏 O(n²)
 *   2. 尾递归优化：先排小区间，用迭代替代大区间递归
 *
 * 编译: gcc -Wall -Wextra -o quick_opt solution_41_quick_sort_optimized.c
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int partition(int arr[], int lo, int hi) {
    int pivot = arr[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[hi]);
    return i + 1;
}

/* 随机化分区 */
int randomized_partition(int arr[], int lo, int hi) {
    int r = lo + rand() % (hi - lo + 1);
    swap(&arr[r], &arr[hi]);
    return partition(arr, lo, hi);
}

/* 优化版快排：随机 pivot + 尾递归优化 */
void quicksort(int arr[], int lo, int hi) {
    while (lo < hi) {
        int p = randomized_partition(arr, lo, hi);
        /* 先递归处理较小的子数组，用迭代处理大的 */
        if (p - lo < hi - p) {
            quicksort(arr, lo, p - 1);
            lo = p + 1;               /* 右半通过 while 迭代处理 */
        } else {
            quicksort(arr, p + 1, hi);
            hi = p - 1;               /* 左半通过 while 迭代处理 */
        }
    }
}

int main(void) {
    srand((unsigned int)time(NULL));  /* 初始化随机种子 */

    char line[1024];
    fgets(line, sizeof(line), stdin);

    int arr[1024], n = 0;
    char *tok = strtok(line, " \n");
    while (tok) {
        arr[n++] = atoi(tok);
        tok = strtok(NULL, " \n");
    }

    quicksort(arr, 0, n - 1);

    for (int i = 0; i < n; i++) {
        if (i > 0) printf(" ");
        printf("%d", arr[i]);
    }
    printf("\n");
    return 0;
}

课堂讨论

讨论答案

Q1: 快排为什么在有序输入下退化？如何用随机化避免？

有序输入 [1,2,3,4,5] 选末位 pivot 时，每次 pivot 都是最大值，分区极不平衡（一边 n-1，一边 0），递归树退化为深度 n 的单链，每层 partition 扫描递减的 n 个元素，总和 ~ n(n-1)/2 = O(n²)。

随机化：分区前 swap(arr[random], arr[hi])，pivot 不再由数据排列决定，期望下每次分区接近二分。虽然仍可能运气差选到最值，但概率极低——连续 k 次选到最坏 pivot 的概率为 (2/n)^k。

三数取中：对已排序和逆序输入，中位数恰好是中间元素，完美二分。

Q2: Lomuto 和 Hoare 分区，谁的交换次数更少？为什么？

Hoare 更少（平均约 1/3 的交换次数）。原因：

Lomuto：每个 ≤pivot 的元素都触发一次 swap(arr[i], arr[j])——即使该元素原本就在正确位置。例如已排序数组，每个元素都自交换一次。
Hoare：仅在两端各找到一个"错位"元素时才交换——只交换真正需要跨过分界线的元素对。

但 Hoare 每次交换可能动两个"都错位"的元素，效率更高。代价是返回值语义更复杂（返回分界点而非 pivot 位置）。

Q3: 三路划分（荷兰国旗问题）在什么场景下比标准快排快？快多少？

场景：大量重复元素的数组（如只有 0/1/2 三种值）。

加速原理：标准快排遇到相等元素时仍会分区和递归；三路快排将 ==pivot 段一次性排除，跳过所有相等元素的递归。极端情况下（如全相同数组），三路快排一次调用完成排序 = O(n)，而标准快排 O(n log n)。

参考数据：100 万个元素、10 个唯一值 → 三路快排约比标准 Lomuto 快 5-10 倍。

Q4: Introsort 为什么选堆排兜底，而不用归并？

原因有三：

堆排是原地的（O(1) 额外空间），归并需要 O(n) 临时数组——introsort 的承诺是整个排序 O(log n) 空间，归并会破坏这个保证
堆排切换零开销：对子数组直接调 heapsort_range(arr, lo, hi)，无需分配/释放内存，切换成本极低
最坏 O(n log n)：堆排无论什么输入都是 O(n log n)，适合作为"保险丝"

归并虽然在缓存局部性上优于堆排，但原地性是 introsort 作为通用排序算法的硬需求。

Q5: 快排、归并、堆排——如果你的数据已经存在链表中，选哪个？为什么？

选归并排序。原因：

链表的归并不需要 O(n) 额外空间——合并两个有序链表只需要修改指针，零额外分配
链表的快排需要随机访问（partition 需要以 pivot 划分元素），链表不支持 O(1) 随机访问
堆排通常依赖数组的索引计算（parent = i/2），不适合链表

因此链表排序的标准答案就是归并排序。这也解释了为什么 std::list::sort 实现为归并排序。

Q6: 写一个 partition 的递归实现（不用循环）可行吗？为什么通常不这样做？

理论上可行，但很丑且没必要：

// 递归版 partition（仅供思考，不建议使用）
int partition_rec(int arr[], int lo, int hi, int i, int j) {
    if (j >= hi) { /* 扫描完成 */ swap(&arr[i+1], &arr[hi]); return i+1; }
    if (arr[j] <= arr[hi]) { i++; swap(&arr[i], &arr[j]); }
    return partition_rec(arr, lo, hi, i, j + 1);
}

不推荐理由：

partition 是 O(n) 操作——用递归会溢出栈（n 大时递归深度 = n）
循环版代码更短、更清晰、更安全
递归版失去了循环的局部性优势（每次递归调用都有函数调用开销）

循环是 partition 的自然选择，递归是 quicksort 的自然选择——各用所长。

课后练习

练习 1：三数取中快排

实现使用三数取中法选择 pivot 的快速排序 median_quicksort。验证它对已排序数组 [1,2,3,4,5,6,7,8] 的 partition 调用次数显著少于标准 Lomuto 版本。

知识点提示：三数取中、最坏情况防御、partition 调用计数

参考解答

#include <stdio.h>

void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

int partition(int arr[], int lo, int hi) {
    int pivot = arr[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; j++)
        if (arr[j] <= pivot) { i++; swap(&arr[i], &arr[j]); }
    swap(&arr[i + 1], &arr[hi]);
    return i + 1;
}

void median_quicksort(int arr[], int lo, int hi) {
    if (lo >= hi) return;
    // 三数取中
    int mid = lo + (hi - lo) / 2;
    if (arr[lo] > arr[mid]) swap(&arr[lo], &arr[mid]);
    if (arr[lo] > arr[hi])  swap(&arr[lo], &arr[hi]);
    if (arr[mid] > arr[hi]) swap(&arr[mid], &arr[hi]);
    swap(&arr[mid], &arr[hi]);  // 中位数放到末尾
    int p = partition(arr, lo, hi);
    median_quicksort(arr, lo, p - 1);
    median_quicksort(arr, p + 1, hi);
}

int main(void) {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    median_quicksort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

对已排序的 8 个元素：三数取中 pivot 始终是中间元素，递归树完美二分，partition 调用 7 次（接近最优）。标准 Lomuto 每次只减少 1 个元素，partition 也调用 7 次但每层比较次数为 n-1, n-2, ...（更多比较）。

练习 2：实现三路快排

实现荷兰国旗三路快排 three_way_qsort，并排序含大量重复元素的数组 [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4]，验证 == pivot 段被正确跳过。

知识点提示：三路划分、lt/i/gt 三指针、arr[i] > pivot 时 i 不前进

参考解答

#include <stdio.h>

void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

void three_way_qsort(int arr[], int lo, int hi) {
    if (lo >= hi) return;
    // 选 arr[lo] 为 pivot（简化）
    int pivot = arr[lo];
    int lt = lo, i = lo, gt = hi;
    while (i <= gt) {
        if (arr[i] < pivot) {
            swap(&arr[lt], &arr[i]); lt++; i++;
        } else if (arr[i] > pivot) {
            swap(&arr[i], &arr[gt]); gt--;
        } else {
            i++;
        }
    }
    three_way_qsort(arr, lo, lt - 1);
    three_way_qsort(arr, gt + 1, hi);
}

int main(void) {
    int arr[] = {3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4};
    int n = sizeof(arr) / sizeof(arr[0]);
    three_way_qsort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

练习 3：编写 partition 调用计数器

修改标准快排，在 partition 函数中用静态变量统计调用次数。分别对随机数组和有序数组测试，观察两者的 partition 调用次数差异，验证最坏 O(n²) 的空间栈深度（递归调用次数）为 n-1 而非 ~log₂ n。

知识点提示：递归深度分析、partition 调用关系、有序 vs 随机输入对比

参考解答

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int partition_calls = 0;
int max_recursion_depth = 0;

void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

int partition(int arr[], int lo, int hi) {
    partition_calls++;
    int pivot = arr[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; j++)
        if (arr[j] <= pivot) { i++; swap(&arr[i], &arr[j]); }
    swap(&arr[i + 1], &arr[hi]);
    return i + 1;
}

void quicksort(int arr[], int lo, int hi, int depth) {
    if (depth > max_recursion_depth) max_recursion_depth = depth;
    if (lo >= hi) return;
    int p = partition(arr, lo, hi);
    quicksort(arr, lo, p - 1, depth + 1);
    quicksort(arr, p + 1, hi, depth + 1);
}

void test(char *label, int arr[], int n) {
    partition_calls = 0;
    max_recursion_depth = 0;
    quicksort(arr, 0, n - 1, 1);
    printf("%s: partition调用=%d, 最大深度=%d\n",
           label, partition_calls, max_recursion_depth);
}

int main(void) {
    srand((unsigned int)time(NULL));
    int n = 1000;

    int *sorted = malloc(n * sizeof(int));
    int *random = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        sorted[i] = i + 1;             /* 有序 */
        random[i] = rand() % 10000;    /* 随机 */
    }

    test("有序数组 (最坏)", sorted, n);
    test("随机数组 (平均)", random, n);

    free(sorted);
    free(random);
    return 0;
}

运行示例：

有序数组 (最坏): partition调用=999, 最大深度=999
随机数组 (平均): partition调用=~700, 最大深度=~30

有序数组的深度 999 ≈ n，随机数组深度 ~30 ≈ log₂(1000)。partition 调用次数和递归深度都反映了分区平衡度。

练习 4：实现 Hoare 分区快排

用 Hoare 分区重写快排，注意递归边界的差异（Hoare 返回分界点 j，左递归到 j 而非 j-1）。对比 Lomuto 和 Hoare 在对随机 10000 个元素排序时的交换次数。

知识点提示：Hoare 分区、双向指针扫描、返回语义差异、递归边界 quicksort(lo, j) vs quicksort(lo, p-1)

参考解答

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int swap_count = 0;

void swap(int *a, int *b) {
    int t = *a; *a = *b; *b = t;
    swap_count++;
}

int hoare_partition(int arr[], int lo, int hi) {
    int pivot = arr[lo];
    int i = lo - 1, j = hi + 1;
    while (1) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        if (i >= j) return j;
        swap(&arr[i], &arr[j]);
    }
}

void hoare_quicksort(int arr[], int lo, int hi) {
    if (lo >= hi) return;
    int j = hoare_partition(arr, lo, hi);
    hoare_quicksort(arr, lo, j);
    hoare_quicksort(arr, j + 1, hi);
}

int main(void) {
    srand(42);
    int n = 10000;
    int *arr = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) arr[i] = rand();

    swap_count = 0;
    hoare_quicksort(arr, 0, n - 1);
    printf("Hoare 交换次数: %d\n", swap_count);

    /* 重新随机填充，用 Lomuto 测试 */
    for (int i = 0; i < n; i++) arr[i] = rand();

    /* Lomuto 部分省略... 预期 Hoare 交换次数约 Lomuto 的 1/3 */

    free(arr);
    return 0;
}

关键差异：Hoare return j 后，递归调用 quicksort(lo, j)（包含 j 而非 j-1），因为 pivot 可能留在左区间任何位置。Lomuto return i+1 后递归 quicksort(lo, p-1)（排除 p），因为 pivot 已确定归位。

练习 5：模拟 Introsort 深度切换

实现一个简化版 introsort：以标准快排为基础，添加 depth_limit 参数（初始值为 2 * log₂(n)，整数部分即可），当 depth_limit == 0 时切换到冒泡排序（替代堆排以简化实现）。测试构造的最坏输入，验证切换机制被触发。

知识点提示：introsort 原理、递归深度监控、混合排序策略、depth_limit 计算和递减

参考解答

#include <stdio.h>
#include <math.h>

void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

/* 简化堆排: 使用冒泡排序作为兜底（教学简化，实际用堆排） */
void bubble_sort(int arr[], int lo, int hi) {
    for (int i = lo; i <= hi; i++)
        for (int j = lo; j < hi - (i - lo); j++)
            if (arr[j] > arr[j + 1])
                swap(&arr[j], &arr[j + 1]);
}

int partition(int arr[], int lo, int hi) {
    int pivot = arr[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; j++)
        if (arr[j] <= pivot) { i++; swap(&arr[i], &arr[j]); }
    swap(&arr[i + 1], &arr[hi]);
    return i + 1;
}

void introsort(int arr[], int lo, int hi, int depth_limit) {
    if (lo >= hi) return;

    if (depth_limit == 0) {
        bubble_sort(arr, lo, hi);
        printf("  [切换兜底] depth_limit=0, 区间 [%d, %d], 用冒泡排序\n", lo, hi);
        return;
    }

    int p = partition(arr, lo, hi);
    introsort(arr, lo, p - 1, depth_limit - 1);
    introsort(arr, p + 1, hi, depth_limit - 1);
}

int main(void) {
    // 构造最坏输入：有序数组 + 末位 pivot = O(n²)
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
    int n = sizeof(arr) / sizeof(arr[0]);
    int depth_limit = 2 * (int)(log2(n));  /* 2 * log₂(16) = 8 */

    printf("n=%d, depth_limit=%d\n", n, depth_limit);
    introsort(arr, 0, n - 1, depth_limit);

    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

运行结果分析：n=16，depth_limit=8。对有序数组当递归深度超过 8 时，剩余子数组（从深度 9 开始）将全部由冒泡排序（实际中用堆排）完成。若无深度保护，快排在最坏输入下会继续 O(n²) 分区到底。

参考资料

《算法导论》（CLRS）第 7 章快速排序 — 最权威的快排教材，包含严格的期望时间复杂度证明和 Hoare 分区分析
Hoare, C.A.R. "Quicksort", The Computer Journal, 5(1):10–16, 1962 — Tony Hoare 的原始论文，提出快速排序算法（现已全文开放获取）
Musser, David R. "Introspective Sorting and Selection Algorithms", Software: Practice and Experience, 27(8):983–993, 1997 — Introsort 的提出论文，阐述递归深度阈值的设计原理
Dijkstra, E.W. "A Discipline of Programming", Chapter 14, Prentice-Hall, 1976 — 荷兰国旗问题的原始出处，Dijkstra 用"红白蓝旗"比喻三路划分
Bentley, J. & McIlroy, M. "Engineering a Sort Function", Software: Practice and Experience, 23(11):1249–1265, 1993 — 描述实际系统中实现高效排序函数的工程经验（三数取中、小数组优化、三路划分）
Sedgewick, R. "Implementing Quicksort Programs", Communications of the ACM, 21(10):847–857, 1978 — 对快排实现细节的全面分析，包括小数组的 cut-off 策略和 pivot 选择方案对比
Jon Bentley, Programming Pearls, 第 11 章 (Sorting) — 用易懂的方式讲解快排工程优化，包括插入排序对小数组的性能优势

Lesson 41: 快速排序 ​

练习任务 ​

核心知识点 ​

代码框架 ​

深度讲解 ​

4.1 分治：划分 → 递归 → 无需合并 ​

4.2 Lomuto 分区：全程逐轮跟踪 ​

4.3 Pivot 落在最终位置：不变式的力量 ​

4.4 有序输入 + 末位 pivot → 最坏 O(n²)：逐轮跟踪证明 ​

4.5 随机化 pivot 与三数取中：修复最坏情况 ​

4.5.1 随机化 pivot ​

4.5.2 三数取中（Median of Three） ​

4.6 Lomuto vs Hoare 划分：完整对比 ​

Hoare 分区伪代码 ​

完整对比表 ​

4.7 快排 vs 归并 vs 堆排：三大 O(n log n) 排序全方位对比 ​

缓存局部性详解 ​

4.8 三路划分：荷兰国旗问题 ​

4.8.1 需求场景 ​

4.8.2 算法 ​

4.8.3 逐步演示 ​

4.9 Introsort：快排 + 堆排的混合策略 ​

4.9.1 动机 ​

4.9.2 深度阈值的计算 ​

4.9.3 Introsort 伪代码 ​

参考解答 ​

课堂讨论 ​

讨论答案 ​

课后练习 ​

练习 1：三数取中快排 ​

练习 2：实现三路快排 ​

练习 3：编写 partition 调用计数器 ​

练习 4：实现 Hoare 分区快排 ​

练习 5：模拟 Introsort 深度切换 ​

参考资料 ​

Lesson 41: 快速排序

练习任务

核心知识点

代码框架

深度讲解

4.1 分治：划分 → 递归 → 无需合并

4.2 Lomuto 分区：全程逐轮跟踪

4.3 Pivot 落在最终位置：不变式的力量

4.4 有序输入 + 末位 pivot → 最坏 O(n²)：逐轮跟踪证明

4.5 随机化 pivot 与三数取中：修复最坏情况

4.5.1 随机化 pivot

4.5.2 三数取中（Median of Three）

4.6 Lomuto vs Hoare 划分：完整对比

Hoare 分区伪代码

完整对比表

4.7 快排 vs 归并 vs 堆排：三大 O(n log n) 排序全方位对比

缓存局部性详解

4.8 三路划分：荷兰国旗问题

4.8.1 需求场景

4.8.2 算法

4.8.3 逐步演示

4.9 Introsort：快排 + 堆排的混合策略

4.9.1 动机

4.9.2 深度阈值的计算

4.9.3 Introsort 伪代码

参考解答

课堂讨论

讨论答案

课后练习

练习 1：三数取中快排

练习 2：实现三路快排

练习 3：编写 partition 调用计数器

练习 4：实现 Hoare 分区快排

练习 5：模拟 Introsort 深度切换

参考资料