第 10 章：排序算法（下）

---

元数据卡

属性	值
难度	（核心型）
前置	第 9 章（排序上）、递归、二叉树 / 堆
关键词	快速排序·Lomuto 分区·Hoare 分区·堆排序·计数排序·基数排序·排序稳定性·比较下界
预计阅读	100 分钟
代码行	~200 行（三语言合计）

---

你的进度

上一章你学会了基本的排序，但森林深处的战斗还没结束——有人在用更狠的招数：随机选一个支点把东西劈成两半各自排、或者塞进桶里不管顺序直接倒出来。速度比你快十倍。

上一章你打完了排序的「常规赛」：选择、冒泡、插入、希尔、归并。归并排序已经让你尝到了分治的甜头——无论输入好坏都是 O(n log n)，但它吃空间。

现在进入下半场，我们抛弃「稳定可预测」的保守策略，赌一把。快速排序赌的是「我随机选个支点，大概率能均分数组」。堆排序赌的是「堆的性质足够强，强到不需要额外内存也能 O(n log n)」。而计数 / 基数 / 桶排序赌的是「我比你的数据，不开比较也能排序」。

最后，我们要面对一个数学定理的拷问：比较排序，最快能有多快？

老陈把前两章学过的排序卡片在你面前摊开——"前几种是通用武器，后三种是专门对付某种阵型的。你都得会区别什么时候用哪一个。"

---

你的任务

本章分层

• 必读：快速排序（Lomuto 分区、随机选 pivot）；堆排序（建堆 + 弹出堆顶）；计数排序（利用数据范围而非比较）
• 选读：快速排序的 Hoare 分区；快速排序的优化（三数取中、小数组切插入）
• 进阶：基数排序（按位计数排序 k 次）；桶排序；比较排序的 O(n log n) 下界（决策树模型）

本章不会要求你掌握

• 基数排序的负数处理
• 比较下界的严格数学推导（了解决策树的概念即可）
• Introsort 的实现细节

读完本章，你应当能：

1. 徒手写快速排序（Lomuto 分区 + 随机选 pivot）
2. 实现堆排序全过程：建堆 → 依次弹出堆顶
3. 解释计数排序的原理和适用场景
4. 判断排序算法是否稳定
5. （选）对比了解基数排序和桶排序
6. （选）理解比较排序的 O(n log n) 下界——决策树模型

---

遭遇战→获得技能

① 快速排序（Quick Sort）—— 分治的叛逆者

核心直觉：选一个 pivot（支点），把比它小的放左边，比它大的放右边。左右分别递归。

老陈用树枝在泥地上画了一个支点——"选一个数当标杆，比它小的扔左边，比它大的扔右边。两边各自递归。" Lomuto 分区是最直观的实现方式：

1.1 Lomuto 分区 —— 简单但慢一点

Lomuto 分区只有两层循环，但每次 swap 的是 i 和 j，扫到的比 pivot 大的元素会被「堆」到右侧：

def quicksort_lomuto(arr low high):
 """快速排序（Lomuto 分区）"""
 if low < high:
 p = partition_lomuto(arr low high)
 quicksort_lomuto(arr low p - 1)
 quicksort_lomuto(arr p + 1 high)
 return arr


def partition_lomuto(arr low high):
 """Lomuto 分区方案"""
 pivot = arr[high] # 选最后一个元素作 pivot
 i = low - 1 # i 是「小值区域」的右边界

 for j in range(low high):
 if arr[j] <= pivot:
 i += 1
 arr[i] arr[j] = arr[j] arr[i]

 arr[i + 1] arr[high] = arr[high] arr[i + 1]
 return i + 1 # 返回 pivot 最终位置

test = [10 7 8 9 1 5]
print(quicksort_lomuto(test 0 len(test) - 1)) # → [1 5 7 8 9 10]

这为什么能工作？

想象一个扫地机器人——i 标记「已扫干净」的边界，j 探路。每发现一个小于 pivot 的元素，就把它扔到 i+1 的位置。最终 pivot 落在大小区域的分界线上。

1.2 Hoare 分区 —— 更快，也更 tricky

def quicksort_hoare(arr low high):
 """快速排序（Hoare 分区）"""
 if low < high:
 p = partition_hoare(arr low high)
 quicksort_hoare(arr low p)
 quicksort_hoare(arr p + 1 high)
 return arr


def partition_hoare(arr low high):
 """Hoare 分区方案——更高效的交换"""
 pivot = arr[low] # 选第一个元素作 pivot
 i = low - 1
 j = high + 1

 while True:
 i += 1
 while arr[i] < pivot:
 i += 1

 j -= 1
 while arr[j] > pivot:
 j -= 1

 if i >= j:
 return j

 arr[i] arr[j] = arr[j] arr[i]

Lomuto vs Hoare

	Lomuto	Hoare
pivot 位置	最终落在分区点上	不一定在分区点
swap 次数	多（~n 次）	少（~n/2 次）
重复元素	相等也 swap，性能下降	相等也 swap
实现难度	简单	中等（边界容易错）

面试考 Lomuto，工程用 Hoare。

1.3 优化版：三数取中 + 随机 pivot + 小数组用插入

import random


def quicksort_optimized(arr low high):
 """优化快排：三数取中 + 随机 + 小数组插入转换"""
 while low < high:
 # 小数组切割：长度小于 10 改用插入
 if high - low < 10:
 insertion_sort_range(arr low high)
 break

 # 三数取中选 pivot
 mid = (low + high) // 2
 if arr[mid] < arr[low]:
 arr[low] arr[mid] = arr[mid] arr[low]
 if arr[high] < arr[low]:
 arr[low] arr[high] = arr[high] arr[low]
 if arr[mid] < arr[high]:
 arr[mid] arr[high] = arr[high] arr[mid]

 p = partition_hoare(arr low high)

 # 尾递归优化：递归处理较短的那一侧
 if p - low < high - p:
 quicksort_optimized(arr low p)
 low = p + 1
 else:
 quicksort_optimized(arr p + 1 high)
 high = p


# 小数组插入排序（用于优化）
def insertion_sort_range(arr low high):
 for i in range(low + 1 high + 1):
 key = arr[i]
 j = i - 1
 while j >= low and arr[j] > key:
 arr[j + 1] = arr[j]
 j -= 1
 arr[j + 1] = key


test2 = [random.randint(0 100) for _ in range(30)]
quicksort_optimized(test2 0 len(test2) - 1)
print(test2[:5] "..." test2[-5:]) # 确认已有序

C++ 快速排序迭代器版

template<typename It>
void quickSort(It first It last) {
 if (std::distance(first last) <= 1) return;

 auto pivot = *std::next(first std::distance(first last) / 2);
 auto mid1 = std::partition(first last [pivot](const auto& v) { return v < pivot; });
 auto mid2 = std::partition(mid1 last [pivot](const auto& v) { return !(pivot > v); });

 quickSort(first mid1);
 quickSort(mid2 last);
}

C++ 标准库的 std::partition 已经替你实现了 Hoare 风格的分区——这就是为什么了解分区原理比背代码更重要。

---

② 堆排序（Heap Sort）—— 二叉堆扮演主角

核心直觉：把数组建成大顶堆，堆顶就是最大值。弹出堆顶，剩下的再调整成堆，重复 n 次。

第 7 章我们学过二叉堆。堆排序就是用堆这个数据结构反复取最大值的过程——不需要写递归，不需要额外数组，O(n log n)，原地完成。

Python 实现（上浮式建堆）

def heapify(arr n i):
 """维护以 i 为根的大顶堆（递归版）"""
 largest = i
 left = 2 * i + 1
 right = 2 * i + 2

 if left < n and arr[left] > arr[largest]:
 largest = left
 if right < n and arr[right] > arr[largest]:
 largest = right

 if largest != i:
 arr[i] arr[largest] = arr[largest] arr[i]
 heapify(arr n largest)


def heap_sort(arr):
 """堆排序：建堆 → 反复提取堆顶"""
 n = len(arr)

 # Phase 1: 建堆（从最后一个非叶子节点开始）
 for i in range(n // 2 - 1 -1 -1):
 heapify(arr n i)

 # Phase 2: 逐一弹出堆顶
 for i in range(n - 1 0 -1):
 arr[0] arr[i] = arr[i] arr[0] # 堆顶（最大）→ 数组末尾
 heapify(arr i 0) # 调整剩余部分为堆

 return arr

print(heap_sort([12 11 13 5 6 7])) # → [5 6 7 11 12 13]

建堆过程演示（n = 6）

初始数组: [12 11 13 5 6 7]

索引 2（13）：左右子 6、7 → 无需调整
索引 1（11）：左右子 5、6 → 11 > 6，不动
索引 0（12）：左右子 11、13 → 13 最大，交换得 [13 11 12 5 6 7]
 递归调整 12：左右子 6、7 → 12 > 7，不动

建堆完成: [13 11 12 5 6 7]

为什么建堆是 O(n) 而不是 O(n log n)？

数学原因：第 k 层有 n/2^(k+1) 个节点，每个节点最多下沉 k 次。

$$ \sum_{k=0}^{\log n} \frac{n}{2^{k+1}} \cdot k \approx n $$

所以建堆是 O(n) 的，不是 O(n log n)。很多人在面试里栽在这个细节上。

Java 对比

void heapSort(int[] arr) {
 int n = arr.length;
 for (int i = n / 2 - 1; i >= 0; i--)
 heapify(arr n i);
 for (int i = n - 1; i > 0; i--) {
 int temp = arr[0];
 arr[0] = arr[i];
 arr[i] = temp;
 heapify(arr i 0);
 }
}

void heapify(int[] arr int n int i) {
 int largest = i left = 2*i + 1 right = 2*i + 2;
 if (left < n && arr[left] > arr[largest]) largest = left;
 if (right < n && arr[right] > arr[largest]) largest = right;
 if (largest != i) {
 int swap = arr[i];
 arr[i] = arr[largest];
 arr[largest] = swap;
 heapify(arr n largest);
 }
}

---

线性时间排序——不开比也能排（进阶选读）

本节为进阶内容。 主线先掌握快排/堆排/计数排序即可。基数排序和桶排序在对数据类型有特定要求时使用。

比较排序有一个天花板：O(n log n)。但如果你愿意放弃「通用性」，针对数据的特点，你可以比 O(n log n) 还快。

3.1 计数排序（Counting Sort）

适用场景：数据范围小（比如 0 ~ 1000），数据量大。

def counting_sort(arr):
 """计数排序：利用数据范围而非比较"""
 if not arr:
 return []

 # 1. 确定范围
 k = max(arr)
 counts = [0] * (k + 1)

 # 2. 计数
 for num in arr:
 counts[num] += 1

 # 3. 累加（确定每个数的最终位置）
 for i in range(1 len(counts)):
 counts[i] += counts[i - 1]

 # 4. 反向填充（保证稳定性）
 output = [0] * len(arr)
 for num in reversed(arr):
 output[counts[num] - 1] = num
 counts[num] -= 1

 return output

print(counting_sort([4 2 2 8 3 3 1])) # → [1 2 2 3 3 4 8]

3.2 基数排序（Radix Sort）

适用场景：整数 / 定长字符串，位数不太多（比如 32 位整数）。

def radix_sort(arr):
 """基数排序：按位计数排序 k 次"""
 if not arr:
 return arr

 max_val = max(arr)
 exp = 1 # 当前位（1、10、100...）

 while max_val // exp > 0:
 arr = _counting_sort_by_digit(arr exp)
 exp *= 10

 return arr


def _counting_sort_by_digit(arr exp):
 """按某一位做计数排序"""
 n = len(arr)
 output = [0] * n
 counts = [0] * 10

 for num in arr:
 digit = (num // exp) % 10
 counts[digit] += 1

 for i in range(1 10):
 counts[i] += counts[i - 1]

 for num in reversed(arr):
 digit = (num // exp) % 10
 output[counts[digit] - 1] = num
 counts[digit] -= 1

 return output

print(radix_sort([170 45 75 90 802 24 2 66]))
# → [2 24 45 66 75 90 170 802]

3.3 桶排序（Bucket Sort）

适用场景：数据在区间内均匀分布（比如 [0 1) 上的浮点数）。

def bucket_sort(arr):
 """桶排序：数据分桶 → 桶内排 → 合并"""
 if not arr:
 return arr

 n = len(arr)
 buckets = [[] for _ in range(n)]

 # 分桶
 for num in arr:
 idx = int(num * n) # 假设数据在 [0 1)
 buckets[idx].append(num)

 # 桶内排序（用插入或任何排序）
 for bucket in buckets:
 bucket.sort()

 # 合并
 return [x for bucket in buckets for x in bucket]

三种线性排序对比

	计数	基数	桶
时间	O(n + k)	O(d × (n + b))	O(n + m)
空间	O(k)	O(n + b)	O(n + m)
适用	小范围整数	整数 / 定长字符串	均匀分布浮点数
稳定			取决于桶内算法

---

排序稳定性

定义：如果两个相等元素排序后相对位置不变，算法是稳定的。

为什么重要？

想象一个按「分数」排序的表格，学生已经按「姓名」排过了。你希望同分的学生仍然保持姓名字典序。只有稳定排序能做到。

稳定性速查

稳定	不稳定
冒泡排序	选择排序
插入排序	希尔排序
归并排序	快速排序
计数排序	堆排序
基数排序

为什么归并稳定但快排不稳定？ 因为归并只有合并相邻部分时相等元素取左边的数据。而快排在分区交换时，跨越分区的 swap 会打乱相等元素的相对顺序。

---

比较排序的下界——进阶了解

本节为进阶内容。 知道"比较排序最快就是 O(n log n)"这个结论就够了。

不是我们不够聪明，是数学不允许。

决策树模型：任何一个比较排序，都可以表示为一棵二叉树。

• 叶子节点：一种可能的排列（n! 种）
• 内部节点：一次比较
• 树高：最坏情况下的比较次数

$$ \text{树高} \geq \log_2(n!) = \Omega(n \log n) $$

所以 任何基于比较的排序算法，最坏情况下至少需要 Ω(n log n) 次比较。

这就是为什么计数排序能做到 O(n)——它跳出了「比较」的框架。

---

常见陷阱

快排为什么在实践中快过归并？

1. 缓存友好：快排的访问模式是线性的；归并需要额外数组的读写
2. 原地排序：不消耗额外内存
3. 常数项小：快排的内部循环很简洁

但这不代表快排总是「更好」。需要稳定输出时用归并，内存吃紧时用堆排，数据范围小时用计数。

一个值得深思的问题

排序算法这么多，Python 的 sorted() 和 list.sort() 到底用了哪个？

答案是 TimSort——归并 + 插入的混合体，稳定、自适应、对现实数据极度友好。我们会在后续章节深入它。

---

通关挑战

1. 三路快排：当数组有大量重复元素时（比如 10⁵ 个 0 和 1），标准快排会退化。实现三路分区（< pivot == pivot > pivot）
2. 通用排序引擎：写一个 sort(arr method) 函数，支持传入方法名选择算法
3. 基数排序负数：当前基数排序只支持非负整数。扩展它支持负数
4. 比较器 count：在快排中埋点统计比较次数，验证决策树下界

---

验收标准

• [ ] 能手写快速排序（两种分区都要会）
• [ ] 能手动模拟堆排序的建堆 + 下沉过程
• [ ] 能说出三种线性排序分别什么时候用
• [ ] 能在 O(n) 时间内判断：给定数组能否用计数排序
• [ ] 能口头推导比较排序下界
• [ ] 能判断任意排序算法是否稳定，并给出理由

---

常见卡点

卡点	破解
快排最坏情况 O(n²) 怎么来的	每次 pivot 恰好是最小/最大，分区严重不均衡。随机选 pivot 能让概率几乎为 0
Hoare 分区为什么返回 j 而不是 i	因为 Hoare 约定分区后 [low j] ≤ pivot，[j+1 high] ≥ pivot
堆排序建堆为什么从 n/2 - 1 开始	叶子节点（索引 ≥ n/2）不需要下沉
计数排序的空间和 k 成正比	k 太大时（比如 int 范围）放弃计数排序，改用基数
稳定不重要？	稳定在分布式排序和数据库里极其重要，多字段排序依赖它

---

现在不需要理解

• introsort（C++ std::sort 的默认实现）—— 快排 + 堆排 + 插入的混合体，当快排递归深度超过 log n 时自动切到堆排。工程中的防退化策略，知道这个理念即可。
• 不基于比较的整数排序的下界 —— 虽然比 O(n log n) 快，但受限于数据模型。什么时候能用、什么时候不能用，比算法本身更需要经验判断。

---

旅人笔记

• 快排是平均最快的通用排序，代价是输入敏感和稳定性缺失
• 堆排是不依赖输入的 O(n log n)，但没有快排快
• 线性排序不是魔法——它们把「比较」换成了「对数据特征的利用」，适用范围收窄了
• 比较下界不是 bug，是特性：它告诉你什么时候该换思路
• 排序是面试里最「卷」的章节——不是因为难，而是因为每个面试官都默认你会

一句话记住本章：「通用是快排，省内存是堆排，特殊数据用线性，面试都考。」

---

→ 下一站预告

第 11 章我们会从「排序」这个绝对有效的话题，转向一个更微妙、更古老的领域——搜索：

• 二分搜索及其变体（左边界、右边界、旋转数组）
• 哈希表与 O(1) 查询
• 二叉搜索树和平衡树（AVL、红黑树）

排序是手段，搜索才是目的。做好准备，下一章会用到你在这两章学到的所有比较逻辑。

← 回到第 9 章：排序算法（上）