第08章 线性时间排序 — 章节汇总

章节概览

本章完成了排序算法的理论闭环：首先通过决策树模型证明了比较排序的 $\Omega (n\lg n)$ 下界（8.1 排序的下界），说明归并排序和堆排序是渐近最优的比较排序；然后介绍了三种非比较排序算法——8.2 计数排序、8.3 基数排序和8.4 桶排序，它们利用输入的额外信息（值域范围、位数限制、均匀分布等）突破 $\Omega (n\lg n)$ 下界，在特定条件下实现线性时间排序。

---

8.1 排序的下界

小节	核心主题	关键结论
8.1 排序的下界	比较排序与决策树模型	任何比较排序最坏情况 $\Omega (n\lg n)$

核心思路：比较排序仅通过元素间的比较操作获取顺序信息，其行为可以用一棵决策树表示。排序 $n$ 个不同元素需要区分 $n!$ 种排列，因此决策树至少有 $n!$ 个叶子节点。一棵高度为 $h$ 的二叉树最多有 $2^h$ 个叶子，故 $2^h\ge n!$，即 $h\ge \lg (n!)=\Omega (n\lg n)$。这意味着归并排序和堆排序是渐近最优的比较排序。

---

8.2~8.4 三种非比较排序

小节	核心主题	关键结论	适用条件
8.2 计数排序	COUNTING-SORT	$\Theta (n+k)$，稳定排序	键值为 $[0,k]$ 的整数
8.3 基数排序	RADIX-SORT	$\Theta (d(n+k))$，使用稳定排序作为子程序	键值位数 $d$ 有限
8.4 桶排序	BUCKET-SORT	期望 $O(n)$，最坏 $\Theta (n^2)$	输入均匀分布在 $[0,1)$

核心思路：三种非比较排序分别利用不同的输入特性：

• 计数排序利用键值范围 $k=O(n)$ 的假设，通过计数直接确定每个元素的位置
• 基数排序利用键值位数 $d$ 有限的假设，逐位使用稳定排序（通常是计数排序），$\Theta (d(n+k))$ 时间内完成
• 桶排序利用输入均匀分布的假设，将元素分入 $n$ 个桶，每个桶期望仅含常数个元素，桶内排序后拼接即可

---

本章核心知识点

关键定义

概念	定义	出处
比较排序	仅通过元素间比较获取顺序信息的排序算法	8.1 排序的下界
决策树	表示比较排序在所有可能输入上行为的二叉树	8.1 排序的下界
稳定排序	保持相等元素的相对顺序的排序算法	8.2 计数排序

关键定理

编号	内容	出处
定理 8.1	任何比较排序最坏情况需要 $\Omega (n\lg n)$ 次比较	8.1 排序的下界
引理 8.3	给定 $n$ 个 $d$ 位数，LSD 基数排序能正确排序	8.3 基数排序
引理 8.4	给定 $n$ 个 $b$ 位数和任意 $r\le b$，LSD 基数排序耗时 $\Theta ((b/r)(n+2^r))$	8.3 基数排序
引理 8.1	桶排序中桶 $i$ 的期望元素数 $\mathbb{E}[n_i^2]=2-1/n$	8.4 桶排序
推论 8.2	桶排序的期望运行时间为 $O(n)$	8.4 桶排序

三种非比较排序对比

比较维度	计数排序	基数排序	桶排序
时间	$\Theta (n+k)$	$\Theta (d(n+k))$	期望 $O(n)$
空间	$\Theta (n+k)$	$\Theta (n+k)$	$\Theta (n)$
稳定性	稳定 ✅	取决于子程序	取决于桶内排序
适用条件	整数，$k=O(n)$	位数 $d$ 有限	均匀分布
原地	否	否	否

---

与前序章节的知识关联

前序章节	关联方式
第6章 堆排序	堆排序是渐近最优的比较排序（$\Theta (n\lg n)$）
第7章 快速排序	快速排序期望 $O(n\lg n)$，达到比较排序下界
第5章 概率分析	桶排序的期望分析使用指示器随机变量和期望线性性

---

学习路线

第8章学习路径：
  8.1 排序的下界（理论极限，建立下界意识）
    → 8.2 计数排序（最简单的线性时间排序）
      → 8.3 基数排序（利用计数排序处理多位数）
        → 8.4 桶排序（利用概率假设实现期望线性时间）

学习建议

本章是从”上界”到”下界”的完整闭环。8.1 的决策树证明是理论计算机科学中”下界证明”的经典范例，建议掌握其证明思路。8.2 的计数排序是后续章节的基础——8.3 的基数排序直接使用计数排序作为稳定子程序。8.4 的桶排序分析是第5章概率分析技术的直接应用，建议复习指示器随机变量。

线性时间排序