flowchart TD
A["为什么要排序？<br/>有序才有折半/BST"] --> B["O(n²) 三件套<br/>插入 / 冒泡 / 选择"]
B --> C["突破 O(n²) 三路线"]
C --> D1["希尔：带增量的插入"]
C --> D2["分治：快排 / 归并"]
C --> D3["堆：树形选择"]
B --> E["不比较：基数排序 LSD/MSD"]
A --> F["内存装不下<br/>→ 外部排序：归并"]
F --> G["置换-选择（长段）<br/>败者树（少比较）<br/>最佳归并树（少 I/O）"]
核心概念：
| 概念 | 要点 | 易考点 |
|---|---|---|
| 稳定性 | 相等关键字排序后相对次序不变 | 稳定：插入、冒泡、归并、基数；不稳定：选择、希尔、快排、堆（口诀：“快希选堆”不稳定） |
| 堆 | 完全二叉树 + 双亲 ≥（≤）孩子；不是 BST（左右孩子无序，2020-9 III 错误） | 大根堆次大值一定在根的下一层（2020-9 IV 正确）；建堆自底向上调整 |
| 快排枢轴 | 每趟划分使枢轴落位（其最终位置确定） | “每趟能确定元素最终位置”的算法：冒泡、选择、堆、快排（2012-10、2017-11） |
| 快排最坏 | 已有序时退化为 、递归深度 | 递归次数与划分后处理顺序无关（2010-10 D）；第 k 趟结果特征（2014-11、2019-10） |
| 归并 | 两个有序表合一（2022-10 A）；稳定、 任何情形、 空间 | 与插入排序相比的优势 = 效率（2017-10 III；不是代码短、不是空间少） |
| 希尔 | 按增量分组、组内直接插入（2015-11 A），增量递减至 1 | 由两趟结果反推增量（2014-10：3；2018-10：5, 3） |
| 基数排序 | LSD：从最低位起，按位分配 + 收集（每趟要稳定） | 第 k 趟后的序列（2013-11、2021-10） |