DS-6 排序

数据结构

来源：10-DS6-排序.md · 完整笔记（7 节，未删减）

数据结构模块。排序是 DS-5（折半查找、BST）的前提，也是算法设计与复杂度分析的“演武场”。 408 考法高度模板化：给序列认算法、给算法算趟结果、比较四大属性（时间、空间、稳定性、与初始状态的关系）。

核心问题

这一部分为什么存在？

查找章（DS-5）证明了“有序”的价值（折半 $O(\log n)$ 、BST），那有序从哪来？排序的主线问题链：

怎么排：朴素的 $O(n^2)$ 做法（插入/冒泡/选择）各自利用了什么观察？——插入利用“前缀已有序”、冒泡利用“交换消逆序”、选择利用“每趟定一位”；
能不能突破 $O(n^2)$ ：能，三条路线——加大跨度的插入（希尔）、分治（快排、归并）、利用完全二叉树性质的选择（堆排）；理论下界：基于比较的排序至少 $O(n \log n)$ ；
不比较行不行：行，按“位”分配收集（基数排序） $O(d(n+r))$ ；
内存装不下怎么办：外部排序（归并 + 置换-选择造长归并段 + 败者树减比较 + 最佳归并树省 I/O）——这是“内存 vs 外存”暗线在 DS 中的收官。

四大评价属性：平均/最坏时间、辅助空间、稳定性（相等关键字相对次序是否保持）、性能是否受初始状态影响（2019-7：四者都是选算法的考虑因素）。

概念体系

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 正确）；建堆自底向上调整 $O(n)$
快排枢轴	每趟划分使枢轴落位（其最终位置确定）	“每趟能确定元素最终位置”的算法：冒泡、选择、堆、快排（2012-10、2017-11）
快排最坏	已有序时退化为 $O(n^2)$ 、递归深度 $O(n)$	递归次数与划分后处理顺序无关（2010-10 D）；第 k 趟结果特征（2014-11、2019-10）
归并	两个有序表合一（2022-10 A）；稳定、 $O(n \log n)$ 任何情形、 $O(n)$ 空间	与插入排序相比的优势 = 效率（2017-10 III；不是代码短、不是空间少）
希尔	按增量分组、组内直接插入（2015-11 A），增量递减至 1	由两趟结果反推增量（2014-10：3；2018-10：5, 3）
基数排序	LSD：从最低位起，按位分配 + 收集（每趟要稳定）	第 k 趟后的序列（2013-11、2021-10）

实现机制

1. $O(n^2)$ 三件套的精确区分

直接插入：把 $A[i]$ 插入前缀有序段（边比边移）；初始越有序越快（比较、移动都少——2020-11：大部分有序时优于简单选择的原因 = 比较少 + 移动少，不是辅助空间）。折半插入：找位置用折半（比较降为 $O(n\log n)$ ）但移动次数不变（2012-11）。
冒泡：每趟相邻比较把最大者“浮”到尾；加 flag 可提前终止（初始有序时 $O(n)$ ）。
简单选择：每趟选最小者与当前位交换——比较恒为 $n(n-1)/2$ 次，与初始状态无关，但移动次数少（每趟最多 1 次交换）是它的卖点。

2. 快排（必须能手写划分）

int Partition(int A[], int lo, int hi) {
    int pivot = A[lo];                 // 取首元素为枢轴
    while (lo < hi) {
        while (lo < hi && A[hi] >= pivot) hi--;
        A[lo] = A[hi];                 // 小者填左坑
        while (lo < hi && A[lo] <= pivot) lo++;
        A[hi] = A[lo];                 // 大者填右坑
    }
    A[lo] = pivot;                     // 枢轴落位
    return lo;
}

核心思想：挖坑填数 + 双指针交替向中间扫，一趟后枢轴左侧全 ≤ 它、右侧全 ≥ 它且枢轴到位。“不可能是第 k 趟结果”题型即检查“是否已有 k 个元素到位且各自满足分区性质”。最坏情形 = 每趟极不平衡（如已排序输入），对策：随机选枢轴/三者取中（补充理解）。

3. 堆排序与堆调整（必须理解、会模拟）

建堆：从最后一个非叶结点 $\lfloor n/2 \rfloor$ 起向前逐个向下调整（与较大孩子比较、下沉）， $O(n)$ ；
排序：反复“堆顶（最大）与堆尾交换、范围减一、堆顶向下调整”， $O(n \log n)$ ；
插入：尾部加入后向上调整（与双亲比较上浮）——2011-11（插 18 比 2 次）、2021-11（依次插入的最终堆形态）；
删除堆顶：尾元素补到根后向下调整——2015-10（删 8 重建比 3 次）；2009-9（小根堆插 3）。

4. 外部排序（识别思想 + 会算）

内存一次装不下全部数据 → 只能“分块进内存排序成归并段、再多路归并”，总代价由 I/O 次数决定，三级优化：

置换-选择排序：用堆造初始归并段，平均长度 ≈ 2×内存容量（段越长段数越少，I/O 越少）；
败者树： $k$ 路归并每选一次最小值从 $k-1$ 次比较降为 $\lceil \log_2 k \rceil$ 次；
最佳归并树：归并段按长度加权，构造哈夫曼式归并树使加权 I/O 最小——哈夫曼思想的直接复用（DS-3）；虚段数公式：若 $(n_0 - 1) \bmod (k-1) \neq 0$ ，补 $k - 1 - (n_0-1)\bmod(k-1)$ 个虚段（2019-11：120 段 12 路 → 补 2 个虚段）。

方案比较

算法	平均	最坏	空间	稳定	受初始状态影响
直接插入	$O(n^2)$	$O(n^2)$ （最好 $O(n)$ ）	$O(1)$	✓	大（越有序越快）
冒泡	$O(n^2)$	$O(n^2)$ （最好 $O(n)$ ）	$O(1)$	✓	大
简单选择	$O(n^2)$	$O(n^2)$	$O(1)$	✗	比较次数恒定
希尔	~ $O(n^{1.3})$	$O(n^2)$	$O(1)$	✗	中
快排	$O(n \log n)$	$O(n^2)$	$O(\log n)$ 栈	✗	大（最怕有序）
堆排	$O(n \log n)$	$O(n \log n)$	$O(1)$	✗	小
归并	$O(n \log n)$	$O(n \log n)$	$O(n)$	✓	小
基数	$O(d(n+r))$	同	$O(r)$	✓	无（2015-9：与初始状态无关）

选择策略口诀：要稳要快选归并（舍空间）；要省空间选堆排（舍稳定）；平均最快选快排（怕最坏）；基本有序选插入；小数据随便选。（2016-11：最坏仍 $O(n\log n)$ 且原地 → 堆排；2017-10：选归并的理由只能是效率。）

应用与考法

形态一：由序列特征认算法 / 判趟数：2010-11（基数不基于比较）、2014-11/2019-10（不可能是快排第 k 趟：检查到位元素数与分区性质）、2013-11/2021-10（基数排序第 k 趟后序列）、2014-10/2018-10（由趟结果反推希尔增量）。

形态二：堆操作模拟：2009-9、2011-11、2015-10、2018-11（建堆过程序列）、2020-9（堆的性质辨析）、2021-11。

形态三：属性对比选择：2011-10（快排要随机存取 → 顺序存储）、2012-10/2017-11（每趟定一位的算法集合）、2012-11（折半插入 vs 直接插入）、2015-9/11、2016-11、2017-10、2019-7、2020-11、2022-10。

形态四：外部排序：2019-11（虚段数 = 2）；置换-选择、败者树、最佳归并树多以概念选择出现。

形态五（与 DS-7 衔接）：2021-42（计数排序大题：设计思想 + 代码 + 稳定性分析与修改——稳定性判定的标准做法是看“相等元素的处理顺序是否可颠倒”）。

做题触发词：看到“第 k 趟结果”→ 先想该算法每趟的“不变量”（快排：枢轴到位；冒泡/选择/堆：尾部/头部有序段扩 1；归并：有序子段长度 ×2；基数：低 k 位有序）；看到“增量”→ 分组检验；看到“稳定吗”→ 查口诀“快希选堆不稳定”。

来源：真题markdown/2009-2024统考真题.md 对应题号。

前后联系

向前依赖：DS-1（顺序表是排序的舞台；快排需随机存取）、DS-3（堆 = 完全二叉树；最佳归并树 = 哈夫曼）。
向后引出：
- 有序序列 → DS-5 折半查找/BST（排序的价值兑现处）；
- 归并思想 → 链表代码题的“归并两段”（2019-41 重排题最后一步）、外部排序 → OS 文件与磁盘 I/O（X-4：多路归并的 I/O 优化与磁盘调度同源）；
- 分治（快排/归并）是算法设计范式的代表 → DS-7 代码题思维模板。

闭卷回忆链

排序的价值在哪兑现？（折半查找、BST——接 DS-5）
$O(n^2)$ 三件套各自利用了什么观察？
为什么基于比较的排序最快也只能 $O(n \log n)$ ？（判定树 $n!$ 叶 → 高 $\log n!$ ；补充理解）
突破平方的三条路线是什么？
希尔排序和普通插入是什么关系？组内用什么排？
快排每趟结束什么被确定了？为什么怕已有序输入？
堆为什么不是 BST？建堆为什么自底向上？插入、删除各怎么调整？
归并排序拿什么换稳定性与最坏保证？（ $O(n)$ 空间）
怎么一眼判断算法稳不稳定？（“快希选堆”）
“每趟能确定一个元素最终位置”的算法有哪些？
内存装不下怎么排？三级优化各省什么？（段少/比较少/I/O 少）
给一个待排场景（基本有序/海量数据/要求稳定/只要原地），你选谁？