数据结构第 7 章：排序——七种内部排序的复杂度与稳定性
排序这一章的考点非常集中：每种算法的最好/平均/最坏时间复杂度、空间复杂度、稳定性、适用场景。八种算法看起来多，但真正需要理解透的只有三个：快排的划分、堆的调整、归并的合并。其余几种都是对照物。
一、先定义两个评价维度
内部排序 vs 外部排序：数据是否全部装入内存。
稳定性：若待排序列中两个相等元素 a 原本在 b 前面，排序后 a 仍在 b 前面，则算法稳定。稳定性只在"按多个关键字排序"时才有实际意义（比如先按姓名排、再按成绩排，稳定的算法能保留第一次的顺序）。
不稳定的四种：快速、希尔、选择、堆。口诀"快些选堆"（快=快排，些=希尔，选=选择，堆=堆排）。其余四种（插入、冒泡、归并、基数）都稳定。
二、插入类
直接插入排序：把第 i 个元素插入到前面已排好的序列里，边比较边后移。
- 最好 O(n)（原本基本有序，几乎不移动）
- 平均 / 最坏 O(n²)
- 空间 O(1)，稳定
- 特点：基本有序时效率极高，常作为快排小区间（长度 < 10）的收尾方案（因为对小数组插入排序常数更小）
希尔排序（缩小增量排序）：按增量 d 分组做插入排序，d 逐步缩小到 1。
- 平均 O(n^1.3) 左右（取决于增量序列，没有统一的精确结论，考试通常写 O(n log n)~O(n²) 之间或直接写增量相关）
- 空间 O(1)，不稳定（相同元素可能被分到不同组）
- 增量序列的最后一个必须是 1
三、交换类
冒泡排序：相邻两两比较，大的往后换。
- 最好 O(n)（加"本趟有无交换"的提前终止标志时）
- 平均 / 最坏 O(n²)
- 空间 O(1)，稳定
快速排序：选一个基准（pivot），把序列划分成"小于基准"和"大于基准"两部分，递归处理两侧。
- 平均 O(n log n)，最坏 O(n²)（序列已基本有序且取第一个元素为基准时，退化成单支，递归深度 n）
- 空间 O(log n)（递归栈），最坏 O(n)
- 不稳定
- 优化手段：随机选基准、三数取中、小区间改用插入排序
- 快排是平均性能最好的内部排序，也是实际库函数（qsort）的基础
四、选择类
简单选择排序：每趟从未排序列中选出最小的放到前面。
- 最好 / 平均 / 最坏都是 O(n²)（无论数据如何，比较次数固定 n(n−1)/2）
- 空间 O(1)，不稳定（交换会跨过相等元素）
- 交换次数少（最多 n−1 次），这是它相对冒泡的唯一优势
堆排序：把序列建成大顶堆（或小顶堆），每次取堆顶与末尾交换，然后向下调整。
- 建初堆 O(n)，每次调整 O(log n)，共 n 次 → 总体 O(n log n)（最好/平均/最坏都是）
- 空间 O(1)（原地），不稳定
- 特点：空间最省的 O(n log n) 排序。适合内存紧张、又不允许递归深度的场景（找前 k 大是它的经典应用）
- 下标从 1 开始时：结点 i 的孩子是 2i、2i+1；从 0 开始时是 2i+1、2i+2
五、归并类
二路归并排序：把序列两两分组排序，再两两合并，直到整体有序。
- 最好 / 平均 / 最坏都是 O(n log n)
- 空间 O(n)（需要辅助数组）
- 稳定
- 特点：唯一"稳定 + 保证 O(n log n)"的排序，适合外部排序（多路归并就是文件排序的核心）和对稳定性有要求的场景（如 Java 的 Collections.sort）
六、非比较类
基数排序：按位（个位、十位、百位…）依次做"分配—收集"，每趟用桶（队列）。
- 复杂度 O(d(n+r))，d 是位数，r 是基数（十进制为 10）
- 空间 O(n + r)，稳定（分配收集必须稳定，否则前面几趟白做）
- 不基于比较，所以不受"比较排序下界 O(n log n)"的限制
七、七种排序总表（这张表要能默写）
| 算法 | 最好 | 平均 | 最坏 | 空间 | 稳定性 | 适用 |
|---|---|---|---|---|---|---|
| 直接插入 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | 基本有序、小数组 |
| 希尔 | — | ≈O(n^1.3) | O(n²) | O(1) | 不稳定 | 中等规模、原地 |
| 冒泡 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | 教学、几乎不用 |
| 快速 | O(n log n) | O(n log n) | O(n²) | O(log n) | 不稳定 | 通用首选 |
| 简单选择 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 | 交换代价大时 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 | 内存紧、要最坏保证 |
| 二路归并 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 | 外部排序、要求稳定 |
| 基数 | O(d(n+r)) | 同 | 同 | O(n+r) | 稳定 | 整数/定长字符串 |
易错点：几条容易记混的结论
- 比较类排序的下界是 Ω(n log n)，这是理论下界，任何基于比较的算法都突破不了；基数排序因为不比较所以例外。
- 快排最坏 O(n²) 的触发条件是数据已经有序（且基准取首元素）——"越有序越慢"是它最反直觉的性质。
- 空间复杂度 O(1) 的有：插入、希尔、冒泡、选择、堆（堆排是唯一原地 O(n log n)）。
- 稳定 + O(n log n) 的只有归并（基数是线性对数但要求特定数据类型）。
- 一趟排序结束后能确定一个元素最终位置的：冒泡、快排、选择、堆（这四类每次都能"定死"一个位置）。
这一章在整门课里的位置
排序是第 1 章复杂度分析的第一次大规模实战：八种算法放在一张表里比时间、比空间、比稳定性，比较的正是第 1 章那套评价体系。它依赖第 2 章的顺序表（插入、选择类都要移动元素）和第 5 章的完全二叉树（堆排序）。往后看，第 8 章"折半查找要求有序"、外部排序的多路归并，都以本章为前提。
本篇是《数据结构与算法（93 讲）》第 7 章的知识点摘要。每种排序都有 C 语言实现与手工推演演示，见 课程页；上一章 图，下一章 查找。
相关课程
这篇笔记涉及的主题，我录过对应的视频课程：
- 数据结构与算法（93讲） 93 讲