第8章 排序
第8章 排序¶
⚠️ 堆排序、快速排序和归并排序是本章的重点与难点。 要掌握各算法的思想、排序过程（能动手模拟）、初始状态的影响、时空复杂度、稳定性、适用场景。⚠️ 考试通常以选择题形式考查不同算法的对比，还要能根据序列特点选择最合适的排序方法。
b_343_5【知识树】第8章骨架¶
- 基本概念：稳定性、内部/外部排序、比较与移动
- 插入排序：直接插入、折半插入、希尔
- 交换排序：冒泡、快速
- 选择排序：简单选择、堆排序
- 归并排序（2 路）
- 基数排序
- 外部排序：多路归并、置换-选择、最佳归并树
- 总对照表 + 选型路线
b_343_0；PDF 第 343 页 · b_343_28.1 排序的基本概念¶
稳定性怎么定义？它能衡量算法优劣吗？¶
若 keyᵢ = keyⱼ 且排序前 Rᵢ 在 Rⱼ 之前，排序后 Rᵢ 仍在 Rⱼ 之前，则该算法稳定。
⚠️ 三点要注意： - 稳定性不能用来衡量算法的优劣，只是描述其性质之一 - ⚠️ 当待排序关键字互不重复时，排序结果唯一，此时是否稳定无关紧要 - ⚠️ 证明一个算法不稳定，只需举出一组关键字的反例即可
b_344_2；PDF 第 344 页 · b_344_14内部排序和外部排序怎么分？¶
- 内部排序：排序期间所有元素都存放在内存中
- 外部排序：⚠️ 元素无法全部装入内存，需在排序过程中频繁地在内、外存之间交换数据
⚠️ 内部排序主要涉及两种基本操作：比较和移动 —— 时间复杂度通常取决于比较和移动的次数。 ⚠️ 但并非所有内部排序都基于比较 —— 基数排序就是典型的非比较排序。 ⚠️ 大多数内部排序算法更适用于顺序存储的线性表。
五大类：插入排序、交换排序、选择排序、归并排序、基数排序。
b_344_5；PDF 第 344 页 · b_344_68.2 插入排序¶
直接插入排序的三步和哨兵？¶
待排序表某一时刻的状态：有序序列 L[1…i−1] | L(i) | 无序序列 L[i+1…n] - ① 查找 L(i) 在 L[1…i−1] 中的插入位置 k - ② 把 L[k…i−1] 中的元素依次后移一位 - ③ 把 L(i) 放入位置 k
⚠️ 从 L(2) 开始，共执行 n−1 趟；初始时 L[1] 视为长度为 1 的有序子序列。
for (i = 2; i <= n; i++)
if (A[i] < A[i-1]) {
A[0] = A[i]; // 哨兵，A[0] 不存放元素
for (j = i-1; A[0] < A[j]; --j)
A[j+1] = A[j]; // 向后挪位
A[j+1] = A[0];
}
b_345_6；PDF 第 345 页 · b_345_7直接插入排序的四项性能？¶
- 空间效率：O(1)（仅常数个辅助单元）
- 时间效率：
- ⚠️ 最好（已有序）：每插入一个元素只需一次比较、无须移动 → O(n)
- ⚠️ 最坏（完全逆序）：每趟比较 i−1 次、移动 i−1 个 → O(n²)
- 平均：⚠️ 比较次数和移动次数均约为 n²/4 → O(n²)
- 稳定性：⚠️ 稳定 —— 因为总是从后往前比较，找到位置后才移动
- 适用性：⚠️ 顺序存储和链式存储都适用，采用链式存储时无须移动元素
b_346_3折半插入排序改进了什么？没改进什么？ ★1考¶
⚠️ 直接插入是边比较边移动；折半插入把二者分离 —— 先用折半查找确定插入位置，再统一移动元素。
- 比较次数：⚠️ 约为 O(n log₂n)，仅取决于元素个数 n（不再依赖初始序列）
- ⚠️ 移动次数并未减少，仍依赖初始序列的有序程度 → 时间复杂度仍是 O(n²)
- 空间 O(1)，稳定
- ⚠️ 只适用于顺序存储的线性表（折半查找需要随机访问）
💡 一句话：折半插入省的是"比"，不是"搬"。
★ 考过 2012
b_347_0希尔排序的思想和增量序列？ ★4考¶
⚠️ 立足点：直接插入排序在待排序列接近正序时可提升到 O(n) → 希尔排序（缩小增量排序）就是利用这一特性。
过程：取初始增量 d₁ < n，把表分成 d₁ 个子序列（下标间隔为 d₁）分别做直接插入排序 → 依次取更小增量 d₂, d₃, …（d₁ > d₂ > … > dₜ = 1） → ⚠️ 增量减到 1 时所有记录同属一个子序列且已高度有序，最后一趟直接插入即可。
⚠️ 目前尚未找到理论上最优的增量序列（代码里常用 dk = n/2, n/4, …, 1）。 教材例：第一趟 d₁ = 5（5 个子序列），第二趟 d₂ = 3，最后 d = 1。
★ 考过 2014、2015、2018、2025
b_347_7希尔排序的四项性能？¶
- 空间 O(1)
- 时间：⚠️ 依赖增量序列，精确分析是数学未解难题；n 在常见范围内时约 O(n^1.3)，⚠️ 最坏退化为 O(n²)
- 稳定性：⚠️ 不稳定 —— 相同关键字被划分到不同子表时，可能改变相对次序（教材图 8.2 中两个 49 顺序变了）
- 适用性：⚠️ 仅适用于顺序存储的线性表
💡 代码细节：希尔排序里的 A[0] 只是暂存单元，不是哨兵 —— j ≤ 0 时插入位置已到。
b_348_18.3 交换排序¶
冒泡排序的一趟做了什么？为什么能提前终止？¶
依次比较相邻元素，逆序就交换 —— ⚠️ 每一趟都会把当前未排序部分的最小（或最大）元素放到其最终位置。 - 第一趟把最小元素移到序列首部，第二趟对剩余子序列重复；⚠️ 已确定位置的元素不再参与比较 - ⚠️ 最多进行 n−1 趟
提前终止：⚠️ 用 flag 标志本趟是否发生交换 —— 一趟下来没发生任何交换，说明表已有序，直接 return。 教材例：第五趟结束后未发生交换，算法提前终止。
b_352_3；PDF 第 352 页 · b_352_4冒泡排序的比较次数和移动次数？¶
- 最好（初始有序）：⚠️ 仅需第一趟，n−1 次比较、0 次移动 → O(n)
- 最坏（初始逆序）：n−1 趟，第 i 趟比较 n−i 次，⚠️ 每次交换需要 3 次移动
- 最坏和平均时间复杂度都是 O(n²)，空间 O(1)
💡 "每次交换 3 次移动"是算移动次数时最容易漏的系数。
b_353_2冒泡排序和直接插入排序的"有序"有什么本质区别？¶
- 冒泡排序：⚠️ 每趟产生的有序子序列具有全局有序性 —— 已排序部分的所有元素均小于（或大于）未排序部分的所有元素，每趟能把一个元素精确放到最终位置
- 直接插入排序：⚠️ 只是局部有序 —— 前面那段虽有序，但后面可能还有更小的元素要插进来
冒泡的稳定性与适用性：⚠️ 稳定（相等元素不交换）；⚠️ 顺序存储和链式存储都适用。
b_353_10快速排序一趟划分怎么走？ ★4考¶
⚠️ 取第一个元素为枢轴 pivot，设 i = low、j = high，双向交替扫描： - j 从右向左扫描，找到第一个小于枢轴的元素，复制到 i 所指位置 - i 从左向右扫描，找到第一个大于枢轴的元素，复制到 j 所指位置 - 交替进行，直到 i == j 相遇 - ⚠️ 把枢轴放入 i 所指位置 → 一次划分完成
教材例（49 38 65 97 76 13 27 49）： - 第一趟后：{27 38 13} 49 {76 97 65 49} - 第二趟后：{13} 27 {38} 49 {49 65} 76 {97} - 第三趟后：13 27 38 49 49 {65} 76 97
⚠️ 递归调用的层次结构可以用一棵二叉树表示。
★ 考过 2014、2019、2023、2024
b_354_7Partition 函数的代码要点？ ★1考¶
int Partition(ElemType A[], int low, int high) {
ElemType pivot = A[low]; // 第一个元素做枢轴
while (low < high) {
while (low < high && A[high] >= pivot) --high;
A[low] = A[high]; // 小的移到左端
while (low < high && A[low] <= pivot) ++low;
A[high] = A[low]; // 大的移到右端
}
A[low] = pivot; // 枢轴归位
return low;
}
⚠️ 两个易错点：内层 while 里必须带 low < high 条件；⚠️ 必须先从 high 端开始扫描（因为枢轴取的是 A[low]，低端已"空出"）。
★ 考过 2016
b_355_2快排的时间和空间复杂度？ ★2考¶
⚠️ 核心判据是每层划分是否均衡，不是“有序/乱序”标签本身。
- 空间效率：⚠️ 递归需要系统栈，容量等于递归调用的最大层数
- 最好（每次均分）O(log₂n)；⚠️ 最坏（划分极不平衡，n−1 次递归）O(n)；平均 O(log₂n)
- 时间效率：
- ⚠️ 最坏是每趟都划成 0 与 n−1（或极不均衡），比较次数约 n(n−1)/2 → O(n²)
- 最好（每次等分）O(n log₂n)
- ⚠️ 平均运行时间非常接近最优情况 → 快排是所有内部排序算法中平均性能最优的
改进划分平衡性的两种办法：⚠️ 三数取中法（取首、尾、中间三个元素的中位数做枢轴）；随机选取枢轴。
⚠️ 校订/边界：在本书 pivot=A[low] 这类固定取端点的实现中，单调序列常导致极不均衡；但随机枢轴或三数取中下，“有序”不必然最坏。同理，乱序也不保证最好，仍可能层层选到极值枢轴。
★ 考过 2010、2024
b_355_6快排为什么不稳定？它的划分有什么特点？ ★1考¶
⚠️ 不稳定：划分时若右侧区域有两个相等且都小于枢轴的关键字，交换到左侧后相对位置会改变。 教材反例：L = {3, 2, 2} → 一趟后 {2, 2, 3}，两个 2 的相对次序变了。
⚠️ 考试口径：本书这套按下标从两端扫描的快排要求随机访问，故王道/统考常规分类答“宜采用顺序存储”。工程上可以为链表另写快排变体，但那不是本书 Partition 的直接移植。
⚠️ 与冒泡对照的关键一句：快排每趟划分后并不产生全局有序的子序列，但每趟都能确保枢轴元素被精确放到其最终位置 —— 这正是快排高效的关键。
★ 考过 2011
b_355_118.4 选择排序¶
简单选择排序的比较次数为什么与初态无关？ ★1考¶
第 i 趟从 L[i…n] 中选出最小元素与 L(i) 交换，⚠️ n−1 趟后有序。
- ⚠️ 总比较次数恒为 n(n−1)/2，与序列初态无关 → 时间复杂度恒为 O(n²)
- ⚠️ 总移动次数很少，最多不超过 3(n−1) 次，最好情况（初始有序）为 0 次
- 空间 O(1)
- ⚠️ 不稳定：反例 L = {2, 2, 1} → 一趟后 {1, 2, 2}，两个 2 的次序变了
- ⚠️ 顺序存储和链式存储都适用，尤其适合关键字较少的情况
★ 考过 2025
b_363_10大根堆和小根堆的定义？ ★1考¶
n 个关键字序列 L[1…n] 是堆，当且仅当（1 ≤ i ≤ ⌊n/2⌋）： - ⚠️ 大根堆：L(i) ≥ L(2i) 且 L(i) ≥ L(2i+1) —— 最大元素在根，任意非根结点不大于其双亲 - ⚠️ 小根堆：L(i) ≤ L(2i) 且 L(i) ≤ L(2i+1)
⚠️ 可将堆视为一棵完全二叉树。 💡 堆的三大应用：堆排序、Top-K 问题、优先队列（大纲新增"堆的应用"考点）。
★ 考过 2020
b_363_17初始建堆从哪个结点开始？ ★2考¶
⚠️ 策略：按自底向上的顺序（从最后一个分支结点到根），依次对每个分支结点执行自上而下的筛选。 ⚠️ 含 n 个结点的完全二叉树，最后一个分支结点的编号是 ⌊n/2⌋ → 从 i = ⌊n/2⌋ 开始，依次向前处理到 i = 1。
每个结点的调整：若小于左右子结点中的较大者（大根堆），则与该较大子结点交换；⚠️ 交换后可能破坏下层子树的堆性质，必须继续沿该路径向下调整。
教材例：i=4 调 09<32 → i=3 调 78<87 → i=2 调 17<45 → i=1 调 53<87，交换后破坏了 L(3) 子树，再对 L(3) 调整 53<78。
★ 考过 2018、2021
b_364_4建堆为什么是 O(n)？堆排序整体多少？¶
- ⚠️ 堆调整的时间复杂度与树高成正比，为 O(h)
- ⚠️ 构建含 n 个元素的堆时，关键字总比较次数不超过 4n → 建堆时间复杂度 O(n)，可在线性时间内把无序数组建成堆
- 堆排序 = 建堆 O(n) + n−1 次输出调整，每次 O(log₂n)
- ⚠️ 最好、最坏、平均时间复杂度均为 O(n log₂n)，空间 O(1)
void HeapSort(ElemType A[], int len) {
BuildMaxHeap(A, len);
for (int i = len; i > 1; i--) {
Swap(A[i], A[1]); // 堆顶与堆底交换
HeapAdjust(A, 1, i-1); // 剩余 i-1 个重新整理为堆
}
}
b_365_6堆的删除（输出堆顶）怎么调整？ ★2考¶
⚠️ 把堆底元素移到堆顶，然后自上而下筛选：新堆顶与左右孩子中的较大者比较，小于则交换，重复直到恢复堆性质。
教材例：09 移到堆顶 → 与较大者 78 交换 → 破坏了 L(3) 子树 → 继续向下把 09 与 65 交换。
⚠️ HeapAdjust 的代码要点：A[0] 暂存子树根；for (i = 2*k; i <= len; i *= 2) 沿较大子结点向下；if (i < len && A[i] < A[i+1]) i++ 取较大子结点；if (A[0] >= A[i]) break 筛选结束。
★ 考过 2015、2024
b_365_0堆的插入怎么做？ ★2考¶
⚠️ 先把新元素置于堆末端，然后自下而上与父结点比较 —— 违反堆性质就交换，直到满足堆定义。
💡 方向对照（必分清）：插入是自下而上（上浮）；删除后调整是自上而下（下沉）；建堆是自底向上地对每个分支结点做自上而下的筛选。
★ 考过 2009、2011
b_365_9Top-K 问题为什么用小顶堆？ ★1考¶
在 1 亿个数中选最大的 100 个： - 用大小为 100 的数组读入前 100 个数，构建小顶堆 - ⚠️ 依次读入后续数字，小于堆顶则舍弃，否则替换堆顶并向下调整 - 读完后堆中 100 个数即为所求
⚠️ 时间复杂度 O(n log₂k)，空间复杂度 O(k) —— 效率远高于全排序。
💡 要最大的 K 个用小顶堆（堆顶是这 K 个里最小的，好淘汰）；要最小的 K 个用大顶堆。
💡 Quickselect 与定长堆怎么分工？ - 内存中已有、可修改的整个数组，且题目问平均/期望效率：Quickselect 通过 Partition 把第 k 小放到最终位置，它左侧的 k−1 个元素连同它本身构成前 k 小（内部无序），期望 O(n) - 数据流式到达、无法保留全部输入，或要稳定上界：大小为 k 的堆，O(n log k) 时间、O(k) 空间 - Quickselect 用随机枢轴只有期望保证；普通端点枢轴最坏 O(n²)。迭代实现可只用 O(1) 额外空间，递归实现的栈深期望 O(log n)、最坏 O(n)
⚠️ 校订/边界：“堆空间 O(1)”只能在 k 被题目固定为常数时这样写；推广到变量 k 必须写 O(k)。
★ 考过 2022
b_366_2堆排序为什么不稳定？¶
⚠️ 调整过程中相等关键字的元素可能因交换而改变原始相对位置。 教材反例：L = {1, 2, 2}，建堆时可能把第二个 2 换到堆顶变成 {2, 1, 2}，最终虽然仍排成 {1,2,2}，但两个 2 的相对次序已变。
⚠️ 适用性：依赖完全二叉树的随机访问特性 → 仅适用于顺序存储的线性表。
b_366_48.5 归并排序和基数排序¶
2 路归并排序的过程？ ★2考¶
⚠️ 核心思想是"归并" —— 把两个或多个有序序列合并为一个更长的有序序列（不同于基于交换或选择的方法）。
过程：把 n 个记录视为 n 个长度为 1 的有序子表 → 两两归并得 ⌈n/2⌉ 个长度为 2（或 1）的有序子表 → 继续两两归并 → 直到合并成一个长度为 n 的有序表。
Merge() 的做法：⚠️ 先把两个子表的所有元素复制到辅助数组 B → 设两个指针分别指向 B 中两段的起始位置 → 依次比较，较小者放回原数组 A → ⚠️ 一段复制完后，把另一段的剩余部分直接复制到 A。
★ 考过 2011、2022
b_375_8归并排序的趟数和复杂度？ ★1考¶
- 非递归：一趟归并 = 把序列划分为若干长度为 h 的有序段两两归并成 2h —— ⚠️ 每趟需调用 ⌈n/(2h)⌉ 次 Merge()，共 ⌈log₂n⌉ 趟
- 递归（分治）：分解（从中间分两半）→ 递归求解 → 合并
性能：
- ⚠️ 空间 O(n) —— 需要一个与待排序表等长的辅助数组
- 时间：每趟遍历 n 个元素 O(n) × ⌈log₂n⌉ 趟 → ⚠️ 最好、最坏、平均都是 O(n log₂n)（分割过程与初始序列无关）
- ⚠️ 稳定 —— 两元素关键字相等时优先取自前一段（代码里是 if (B[i] <= B[j]) 的那个等号）
- ⚠️ 只需顺序访问 → 顺序存储和链式存储都适用
⚠️ 推广：对 N 个元素做 k 路归并，趟数 m = ⌈log_k N⌉。 💡 代码细节：最后两个 while 循环只会执行一个。
★ 考过 2024
b_376_10基数排序的分配与收集怎么做？ ★2考¶
⚠️ 基数排序不依赖元素间的比较，而基于关键字各位的大小 —— 是借助多关键字排序的思想对单逻辑关键字排序。
两种方向：最高位优先 MSD（按位权递减逐层划分）、最低位优先 LSD（按位权递增依次排序）。
LSD 的每一趟（本质上是一次稳定排序）： - ① 分配：清空 r 个队列，扫描每个结点，当前位关键字为 k 就加入队列 Q_k - ② 收集：⚠️ 按 Q₀ 到 Q_{r−1} 的顺序把各队列连接起来
教材例：278 109 063 930 589 184 505 269 008 083，r = 10，三位数 → 三趟分配收集（个位 → 十位 → 百位）。
★ 考过 2013、2021
b_377_7基数排序的性能为什么与初态无关？ ★1考¶
- ⚠️ 空间 O(r) —— 一趟需要 r 个队列（r 个队头指针 + r 个队尾指针），但各趟可重复使用
- ⚠️ 时间 O(d(n+r)) —— 共 d 趟，每趟分配遍历 n 个元素 O(n)、收集处理 r 个队列 O(r)；与序列初始状态无关
- ⚠️ 稳定 —— 分配按原序列顺序入队，收集按队列编号出队
- ⚠️ 顺序存储和链式存储都适用，链式结构尤其适合
💡 "元素移动次数与序列初态无关"的排序算法：基数排序（还有简单选择排序的比较次数与初态无关，但移动次数有关）。
★ 考过 2015
b_378_5计数排序的四个 for 循环各干什么？ ★4考¶
⚠️ 计数排序不在统考大纲内，但其思想在历年真题中多次涉及。 核心：对每个元素 x 统计小于 x 的元素个数，从而确定 x 的位置（若有 8 个元素小于 x，则 x 排第 9 位）。
for (i=0; i<k; i++) C[i] = 0; // ① 初始化计数数组
for (i=0; i<n; i++) C[A[i]]++; // ② C[x] = 值等于 x 的元素个数
for (i=1; i<k; i++) C[i] += C[i-1]; // ③ C[x] = 小于等于 x 的元素总数
for (i=n-1; i>=0; i--) { // ④ 从后往前遍历
B[C[A[i]]-1] = A[i];
C[A[i]]--;
}
⚠️ 第 ④ 步为什么从后往前：保证 A 中先出现的相同元素在 B 中仍排在前面 → 稳定性。
性能：⚠️ 空间 O(n+k)（不算输出数组则 O(k)）；时间 O(n+k) —— ⚠️ k = O(n) 时可达线性 O(n)，但 k ≫ O(n log₂n) 时反而不如快排、堆排；稳定；仅适用于顺序存储。 ⚠️ 要求待排序元素为非负整数，取值范围不宜过大。
★ 考过 2013、2015、2018、2021
b_378_158.6 内部排序算法的比较与应用¶
八种排序算法的完整性质表？ ★6考¶
| 算法 | 最好 | 平均 | 最坏 | 空间 | 稳定 |
|---|---|---|---|---|---|
| 直接插入排序 | O(n) | O(n²) | O(n²) | O(1) | ✅ |
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | ✅ |
| 简单选择排序 | ⚠️ O(n²) | O(n²) | O(n²) | O(1) | ❌ |
| 希尔排序 | ⚠️ 无精确表达式（约 O(n^1.3)） | — | O(n²) | O(1) | ❌ |
| 快速排序 | O(nlog₂n) | O(nlog₂n) | ⚠️ O(n²) | ⚠️ O(log₂n) | ❌ |
| 堆排序 | O(nlog₂n) | O(nlog₂n) | O(nlog₂n) | O(1) | ❌ |
| 2 路归并排序 | O(nlog₂n) | O(nlog₂n) | O(nlog₂n) | ⚠️ O(n) | ✅ |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | ⚠️ O(r) | ✅ |
⚠️ 一条高频结论：平均时间复杂度为 O(n log₂n) 的算法中，只有归并排序是稳定的。 ⚠️ 快排是唯一最坏会退化到 O(n²) 的"高效"算法；按本书比较表，归并排序的辅助空间开销最多，为 O(n)。
★ 考过 2009、2010、2017、2020、2021、2022、2023、2025
b_386_0；PDF 第 386 页 · b_386_1；PDF 第 386 页 · b_386_2【口诀速记】排序算法三维口诀表¶
| 维度 | 口诀 | 解释 |
|---|---|---|
| 时间复杂度 | 选帽插，都很方 (n²)，插帽最快一发出（最好为 n） | 选择、冒泡、插入都是 O(n²)，插入和冒泡最好情况 O(n) |
| 快归队（堆），n 老二，快速最坏也很方 | 快排、归并、堆排序平均 O(nlogn)，快排最坏 O(n²) | |
| 基哥就是不一样，d 趟都是 n+r | 基数排序是 O(d(n+r))；只有把位数 d 视为固定常数时，才可简写为 O(n+r) | |
| 空间复杂度 | 快老二，归并 n | 快排 O(logn)，归并 O(n) |
| 基数 r 个队列，其余都是 1 | 基数排序 O(r)，其他都是 O(1) | |
| 稳定性 | 不稳定：选艾希堆攻速 | 选择、希尔、堆排、攻速 = 快排 |
| 稳定：插帽龟（归）+ 基你太稳 | 插入、帽（冒泡）、归并、基数排序 |
b_385_8；PDF 第 385 页 · b_385_9；PDF 第 385 页 · b_385_11按王道考试分类，哪些排序算法宜用顺序存储？ ★1考¶
- ⚠️ 本书/统考常规归为顺序存储：折半插入排序、希尔排序、快速排序、堆排序
- ⚠️ 顺序和链式都适用：直接插入排序、冒泡排序、简单选择排序、归并排序、基数排序
💡 记忆法："折希快堆"按书中标准实现依赖随机访问，考试归到顺序存储；其余标准实现都能上链表。 工程上可为链表另写快速排序变体，但选择题没有特殊说明时仍按本书分类作答。
★ 考过 2017
b_385_12；PDF 第 385 页 · b_385_13一趟排序后能确定几个元素的最终位置？ ★1考¶
⚠️ 这是"给中间结果反推算法"类题目的核心判据： - 冒泡排序、简单选择排序、堆排序：⚠️ 每趟处理后都能确定当前最大（或最小）元素的最终位置 - 快速排序：⚠️ 一趟划分后至少能确定一个元素（枢轴）的最终位置，但⚠️ 不产生全局有序子序列 - 直接插入排序：⚠️ 前面那段虽有序，但每个元素都不一定在最终位置 - 归并排序：⚠️ 一趟后是若干长度翻倍的有序段，段内有序、段间无序 - 基数排序：⚠️ 一趟后按当前位有序
★ 考过 2012
b_385_14；PDF 第 385 页 · b_385_15选排序算法要考虑哪五个因素？ ★1考¶
- 待排序元素的个数 n
- 初始状态（是否基本有序）
- 关键字的结构及分布情况
- 对稳定性的要求
- 存储结构类型及辅助空间限制
★ 考过 2019
b_386_6排序算法选型的六条结论？¶
- n 较小 → 直接插入或简单选择；⚠️ 记录本身信息量大时选简单选择（因为直接插入的移动次数通常多于简单选择）
- n 较大 → O(n log₂n) 的三种：⚠️ 关键字随机分布时快排通常最高效；堆排序辅助空间更少且不会退化；⚠️ 既要稳定又要 O(n log₂n) 只能选归并
- 初始基本有序 → 直接插入或冒泡（最好 O(n)）
- ⚠️ 理论下界：基于比较的排序，最坏情况下至少需要 O(n log₂n) 时间（可用判定树证明）
- n 很大且关键字位数少、可分解 → 基数排序，接近线性
- ⚠️ 记录本身信息量大 → 宜用链表存储，此时插入类或归并类更有优势（避免频繁移动大对象）
b_386_98.7 外部排序¶
外部排序的两个阶段和时间瓶颈？ ★1考¶
⚠️ 外部排序 = 待排序记录存在外存、无法一次装入内存，需多次内外存交换数据。 ⚠️ 时间代价主要取决于访问磁盘的次数（I/O 次数） —— 磁盘读写的机械动作耗时远高于内存运算。
两个阶段： - ① 生成初始归并段：按内存缓冲区大小把文件划分为子文件，依次读入内存做内部排序后写回外存，形成有序的初始归并段（顺串） - ② 多路归并：逐趟归并，每趟把多个有序段合并为更长的段
外部排序总时间 = 内部排序时间 + 外存读/写时间 + 内部归并时间，⚠️ 外存读写时间远大于其余两项。
★ 考过 2016
b_392_8；PDF 第 392 页 · b_392_9；PDF 第 393 页 · b_393_2增大归并路数能省多少 I/O？（教材算例）¶
2000 个记录、每块 125 个记录 → 8 个初始归并段，每段 250 条。 内存分三个缓冲区：⚠️ 两个输入缓冲区 + 一个输出缓冲区。 - 2 路归并：3 趟，每趟 16 读 + 16 写 = 32 次 I/O → ⚠️ 32×3 + 32（初始阶段）= 128 次 - 4 路归并：仅 2 趟 → ⚠️ 32×2 + 32 = 96 次
⚠️ 一般地：r 个初始归并段做 k 路归并，归并趟数 S = ⌈log_k r⌉。 💡 所以减少 I/O 的两条路：增大归并路数 k、减少归并段个数 r。
b_393_0为什么增大 k 反而要引入败者树？ ★1考¶
⚠️ 矛盾：增大 k 能减少趟数，但普通多路归并中每次从 k 个元素选最小要比较 k−1 次 → S 趟总比较次数
⚠️ (k−1)/⌈log₂k⌉ 随 k 增大而增大 → 内部归并时间上升，抵消了 I/O 收益。
败者树（树形选择排序的变体，可视为完全二叉树）： - ⚠️ k 个叶结点存 k 个归并段当前参与比较的元素 - ⚠️ 内部结点记录左右子树比较中的"败者"（关键字较大者），胜者继续向上比较 - ⚠️ 最终胜者的段号存于 ls[0]
⚠️ k 路归并的败者树深度为 ⌈log₂k⌉ + 1 → 选最小只需 ⌈log₂k⌉ 次比较 → 总比较次数变成 (n−1)⌈log₂r⌉，⚠️ 与 k 无关。
★ 考过 2024
b_394_6归并路数 k 是不是越大越好？¶
⚠️ 不是。 增大 k 需要增加输入缓冲区的数量 —— 若总内存固定，每个缓冲区容量就变小，每趟归并的外存读写次数增加。 ⚠️ k 过大时，尽管归并趟数减少，总 I/O 次数反而可能增加。
b_395_0置换-选择排序的七个步骤？ ★1考¶
目的：⚠️ 生成更长的初始归并段，从而减少归并段个数 r（普通内部排序生成的段长受限于内存工作区大小）。
设输入文件 FI、输出文件 FO、工作区 WA（容纳 w 个记录）： - ① 从 FI 读入 w 个记录到 WA - ② 从 WA 选出关键字最小的记录，记为 MINIMAX - ③ 把 MINIMAX 写入 FO - ④ 若 FI 非空，从 FI 读入下一个记录到 WA - ⑤ ⚠️ 从 WA 中所有关键字不小于当前 MINIMAX 的记录中选最小者，作为新的 MINIMAX - ⑥ 重复 ③~⑤，直到 WA 中不存在关键字不小于 MINIMAX 的记录 → 一个初始归并段输出完毕 - ⑦ 重复 ②~⑥，直到 FI 与 WA 均为空
⚠️ 段长不再受限于 w，而取决于输入数据的分布；教材例 FI = {17,21,05,44,10,12,56,32,29}，w = 3 → 第一段 05 17 21 44 56（长度 5 > 3），第二段 10 12 29 32。 ⚠️ 选 MINIMAX 的过程需用败者树实现。
★ 考过 2023
b_395_8最佳归并树怎么构造？I/O 次数怎么算？ ★1考¶
⚠️ 叶结点 = 初始归并段，权值 = 段长；叶到根的路径长度 = 该段参与归并的趟数；⚠️ 树的 WPL = 归并过程中读取的总记录数 → 总 I/O 次数 = 2 × WPL。
构造原则：⚠️ 把哈夫曼编码思想推广到 k 叉树 —— 优先归并长度小的段，延后归并长度大的段。
教材算例（9 个段：9,30,12,18,3,17,2,6,24，3 路归并）： 普通方案 I/O = 2×WPL = 484；最佳归并树 = 446。 ⚠️ 8 个段时若强行让最后一次降为 2 路，I/O 高达 386；引入虚段后降至 326。
★ 考过 2013
b_396_7虚段要补几个？ ★1考¶
严格 k 叉树满足：n = n_k + n₀ 且 n = k·n_k + 1 → ⚠️ n₀ = (k−1)·n_k + 1，即 n_k = (n₀−1)/(k−1)。
判断规则： - ⚠️ 若 (n₀ − 1) % (k − 1) = 0 → 正好能构成严格 k 叉归并树，无须补虚段 - ⚠️ 若 (n₀ − 1) % (k − 1) = u ≠ 0 → 需补 k − u − 1 个虚段
教材算例：8 个归并段做 3 路归并，(8−1)%(3−1) = 1 ≠ 0 → ⚠️ 补 3 − 1 − 1 = 1 个虚段，叶结点增至 9，(9−1)%(3−1) = 0 成立。
💡 虚段就是长度为 0 的空归并段，不产生实际 I/O，但能让树形更接近哈夫曼最优形态。
★ 考过 2019
b_397_0【原书试题精选与答案方法】第8章¶
直接插入与折半插入的比较次数、移动次数和适用存储怎样区分？（2012 统考）¶
折半插入只把“在已有序区中找插入位置”改成折半查找，所以要分三层判断：
- 关键字比较次数：直接插入受初态影响；折半插入约为 \(O(n\log n)\)，只主要取决于表长。
- 元素移动次数：两者相同，仍要把插入位置之后的元素整体后移，最坏为 \(O(n^2)\)。
- 总时间与空间：两者总时间仍为 \(O(n^2)\)、空间为 \(O(1)\)；折半插入只适合顺序存储。
因此 2012 第 17 题只有“关键字比较次数”可能不同，选 D。相等关键字应插到原有相等元素之后，二者都可保持稳定。
b_351_11；PDF 第 351 页 · b_351_12希尔排序的分组、增量和每组操作怎样快速判断？（2014、2015、2018 统考）¶
增量为 \(d\) 时，下标相差 \(d\) 的元素属于同一子表，每个子表内部做直接插入排序；增量逐步缩小，最后必须取 \(d=1\)。
- 2014 第 18 题：核对同余下标组，第一趟增量为 3，选 B。
- 2015 第 19 题：各子表采用直接插入排序，选 A。
- 2018 第 20 题：分别检验第一趟后“间隔 5 有序”、第二趟后“间隔 3 有序”，选 D。
⚠️ 一趟希尔排序不是把连续的 \(d\) 段分别排序，而是把下标模 \(d\) 同余的元素分到一组。跨组的相等元素可能换序，所以希尔排序不稳定。
b_351_13；PDF 第 351 页 · b_351_14；PDF 第 351 页 · b_351_15；PDF 第 351 页 · b_351_16；PDF 第 351 页 · b_351_17；PDF 第 351 页 · b_351_20怎样完整写出直接插入排序的每一趟结果？（8.2 综合 01）¶
每趟只取当前元素，向前找到第一个不大于它的位置；被越过的元素整体后移。对 \(\{4,5,1,2,6,3\}\)：
即使当前元素本来就在正确位置，这一趟仍然存在，只是序列不变。手算时可用竖线标出每趟结束后的有序前缀。
b_351_21；PDF 第 351 页 · b_351_22；PDF 第 351 页 · b_351_23；PDF 第 352 页 · b_352_0给定多个增量时，怎样手算希尔排序而不串组？（8.2 综合 02）¶
对 \(\{50,26,38,80,70,90,8,30,40,20\}\)，依次取 \(d=5,3,1\)，每一轮先按下标同余分组，再在组内插入：
核验某轮是否正确，只需逐组检查 \(A[i]\le A[i+d]\le A[i+2d]\)，不能要求整表已经连续有序。
b_352_1快速排序的递归次数和存储结构分别由什么决定？（2010、2011 统考）¶
快排一趟划分后，只对枢轴左右两个非空子表递归。因此递归次数由每次划分是否均衡决定，与先处理左表还是右表无关。2010 第 15 题选 D。
快速排序需要按下标从两端扫描、交换并快速定位子表边界，最适合顺序存储；链表虽可改写，但不能直接发挥这种随机定位优势。2011 第 16 题选 A。
💡 递归树越平衡越快、栈越浅；枢轴反复取到最值时递归树退化为单链，时间和栈空间都会恶化。
b_359_17；PDF 第 360 页 · b_360_0；PDF 第 360 页 · b_360_1；PDF 第 360 页 · b_360_2怎样判断一个序列不可能是快速排序第二趟后的结果？（2014、2019 统考）¶
不要复原完整交换过程，抓“枢轴已归位”这个不变量：每完成一次划分，至少有一个枢轴处在最终位置，且其左边都不大于它、右边都不小于它。
- 第一枢轴若落在端点，第二趟只需划分余下的非空子表，因此两趟后至少有 2 个元素归位，且至少一个在原数组端点。
- 第一枢轴若落在内部，第二趟会把它分出的左右两个非空子表各划分一次，因此两趟后至少有 3 个枢轴归位。
逐项寻找满足左右分区条件的“定界元素”，2014 第 17 题 C、2019 第 18 题 D 无法形成两趟合法划分，故分别选 C、D。
b_360_3；PDF 第 360 页 · b_360_4；PDF 第 360 页 · b_360_5；PDF 第 360 页 · b_360_6怎样由快排中间状态找枢轴，并概括 P、Q 两块的关系？（2023、2024 统考）¶
一个元素若已处在最终位置，且左侧所有元素都不大于它、右侧所有元素都不小于它，就可能是本趟枢轴。
- 2023 第 19 题：81 满足上述条件，选 D。
- 2024 第 20 题：一趟结束后，左块 \(P\) 中任一元素都不大于右块 \(Q\) 中任一元素，但 \(P,Q\) 各自未必有序，选 A。
⚠️ 快排建立的是“块与块之间全序、块内部待排”，不要把一趟结果误认成两个有序段。
b_360_7；PDF 第 360 页 · b_360_8；PDF 第 360 页 · b_360_10；PDF 第 360 页 · b_360_11怎样用一趟划分把所有奇数放在偶数前面？（8.3 综合 01）¶
设左右指针 \(i,j\)。\(i\) 从左找偶数，\(j\) 从右找奇数；若 \(i<j\) 就交换，继续扫描，直到相遇。
while i < j:
while i < j and A[i] is odd: i++
while i < j and A[j] is even: j--
if i < j: swap(A[i], A[j])
每个元素最多被扫描常数次，时间 \(O(n)\)、额外空间 \(O(1)\)。它只完成奇偶分区，不保证奇数内部或偶数内部的原相对顺序，因而通常不稳定。
b_360_12；PDF 第 360 页 · b_360_13；PDF 第 360 页 · b_360_14；PDF 第 360 页 · b_360_15；PDF 第 360 页 · b_360_16；PDF 第 361 页 · b_361_0怎样用快排划分在线性平均时间内找第 k 小元素？（8.3 综合 02）¶
每次划分得到枢轴最终位置 \(m\)：
- \(m=k\)：直接返回枢轴；
- \(m>k\)：只在左子表继续；
- \(m<k\)：只在右子表继续，目标次序仍按全表的 \(k\) 判断，或换算为右表中的第 \(k-m\) 小。
这就是 quickselect。它每层只保留一侧，平均时间 \(O(n)\)；若枢轴连续极端不平衡，最坏仍为 \(O(n^2)\)。空间取决于实现：改写成迭代式原地划分时额外空间为 \(O(1)\)；原书给出的递归写法还要计递归栈，平均约 \(O(\log n)\)、最坏 \(O(n)\)。
b_361_1；PDF 第 361 页 · b_361_2；PDF 第 361 页 · b_361_3；PDF 第 361 页 · b_361_4；PDF 第 361 页 · b_361_5；PDF 第 361 页 · b_361_6；PDF 第 361 页 · b_361_7荷兰国旗问题为什么需要三个边界指针？（8.3 综合 03）¶
维护三个区域：[0,i) 已是红色，[i,j) 已是白色，(k,n-1] 已是蓝色，[j,k] 尚未分类。
蓝色分支交换后不能立刻令 j++，因为从右端换到 A[j] 的元素尚未分类。时间 \(O(n)\)、空间 \(O(1)\)。
b_361_8；PDF 第 361 页 · b_361_9；PDF 第 361 页 · b_361_10；PDF 第 362 页 · b_362_0；PDF 第 362 页 · b_362_1怎样把整数集合分成元素个数最接近、两组和之差最大的两组？（2016 统考综合）¶
设 \(n\) 个元素互异。要让 \(|n_1-n_2|\) 最小，应令一组含 \(\lfloor n/2\rfloor\) 个；要让 \(|S_1-S_2|\) 最大，应把较小的一半全放入一组、较大的一半放入另一组。
用快速选择反复划分，直到第 \(\lfloor n/2\rfloor\) 小元素到达最终位置；其左侧连同该元素构成小元素组，其余构成大元素组，再分别求和。平均时间 \(O(n)\)、额外空间 \(O(1)\)，最坏时间 \(O(n^2)\)。
💡 这题不是完整排序题：只要找到分界秩并完成两侧分区即可。
b_362_2；PDF 第 362 页 · b_362_3；PDF 第 362 页 · b_362_4；PDF 第 362 页 · b_362_5；PDF 第 362 页 · b_362_6；PDF 第 362 页 · b_362_7；PDF 第 362 页 · b_362_8；PDF 第 363 页 · b_363_0；PDF 第 363 页 · b_363_1堆中插入一个元素时，比较次数和最终位置怎样求？（2009、2011、2021 统考）¶
把新元素先放到堆尾，再沿双亲链向上调整；大根堆在新元素大于双亲时交换，小根堆反之。最多比较树高减 1 次，即 \(\lfloor\log_2 n\rfloor\) 量级。
- 2009 第 15 题：在给定小根堆末尾插入 3，沿双亲链上浮，选 A。
- 2011 第 16 题：插入 18 只需与双亲比较 2 次，选 B。
- 2021 第 20 题：强调“依次插入空堆”，须逐个上浮，结果选 B；它不等同于把完整数组一次性自底向上建堆。
b_371_2；PDF 第 371 页 · b_371_3；PDF 第 371 页 · b_371_4；PDF 第 371 页 · b_371_5；PDF 第 371 页 · b_371_6；PDF 第 372 页 · b_372_2；PDF 第 372 页 · b_372_3；PDF 第 372 页 · b_372_5删除堆顶时，怎样计算向下调整过程和比较次数？（2015、2024 统考）¶
先用堆尾覆盖堆顶、堆长减 1，再向下调整。每层先比较两个孩子选出更优者，再与当前元素比较；只有一个孩子时只比一次。
- 2015 第 17 题：删除 8 后，由堆尾 12 覆盖堆顶并下沉，共比较 3 次，选 C。
- 2024 第 21 题：连续删除两次，每次都必须从上一次调整完成的堆继续，最终为 \(\{20,19,15,5,8,12\}\)，选 B。
⚠️ “比较层数”不总等于“关键字比较次数”；双孩子层通常要两次关键字比较。
b_371_8；PDF 第 371 页 · b_371_9；PDF 第 372 页 · b_372_6；PDF 第 372 页 · b_372_7；PDF 第 372 页 · b_372_9；PDF 第 372 页 · b_372_11自底向上建初始堆时，为什么从最后一个分支结点开始？（2018 统考）¶
叶结点天然已是堆，只需从 \(\lfloor n/2\rfloor\) 到 1 逆序对每个分支结点向下调整。每次让当前子树先成为堆，处理到根时整棵完全二叉树即成堆。
2018 第 18 题按这一顺序筛选，结果选 A。建堆总时间是 \(O(n)\)，不是把每个结点都按树高上界粗算得到的 \(O(n\log n)\)：绝大多数结点离叶很近，调整高度很小。
b_371_11；PDF 第 371 页 · b_371_12；PDF 第 371 页 · b_371_13堆到底保证哪些次序关系，第二大元素又在哪里？（2020 统考）¶
堆是顺序存储的完全二叉树，只保证双亲与孩子之间的偏序，不保证兄弟、同层或左右子树之间有序，也不是二叉排序树。
大根堆中最大元素是根；第二大元素必在根的两个孩子中，因为除根外每个结点都不大于自己的祖先。2020 第 19 题中 I、II、IV 正确，选 C。
💡 小根堆的最大元素只能出现在叶结点，但不一定是数组最后一个元素。
b_372_0；PDF 第 372 页 · b_372_1堆与二叉排序树的有序性为什么不能混为一谈？（8.4 综合 01）¶
二者看起来都有父子大小约束，但强度不同：
- 大/小根堆：只要求每个双亲不小于/不大于孩子；左右孩子及两棵子树之间没有次序。
- 二叉排序树：对每个结点，整棵左子树均小于根、整棵右子树均大于根；中序遍历有序，但树形不必完全。
因此堆的层序、先序、中序通常都不能直接得到全局有序序列；BST 的中序可以。
b_372_12；PDF 第 372 页 · b_372_13；PDF 第 372 页 · b_372_14一棵树怎样才能同时是大根堆和二叉排序树？（8.4 综合 02）¶
大根堆要求树是完全二叉树且根大于孩子；BST 又要求右孩子大于根。因此只要出现右孩子，两种条件立即冲突。
同时满足二者的非空树只能是：
- 单个结点；或
- 两个结点，且第二个结点是根的左孩子。
有三个结点的完全二叉树一定有右孩子，已不可能同时满足。
b_372_15；PDF 第 372 页 · b_372_16；PDF 第 373 页 · b_373_0；PDF 第 373 页 · b_373_2只需得到前 k 个最小元素时，为什么可不把全表完全排好？（8.4 综合 03）¶
题目要求前 \(k\) 个位置有序，而其余位置无须有序。可建小根堆并连续取出 \(k\) 次最小值：建堆 \(O(n)\)，每次删除堆顶 \(O(\log n)\)，总时间
比做 \(k\) 趟简单选择或冒泡的 \(O(kn)\) 更适合大表。
💡 “找最小的 \(k\) 个但不要求有序”与“把最小的 \(k\) 个按序放到前面”不同；前者常用大小为 \(k\) 的大根堆，后者还要输出或再排序。
b_373_3；PDF 第 373 页 · b_373_4；PDF 第 373 页 · b_373_5；PDF 第 373 页 · b_373_6；PDF 第 373 页 · b_373_7m 叉堆的双亲、孩子编号及操作复杂度怎样推广？（8.4 综合 04）¶
以 0 为起始下标的 \(m\) 叉堆中：
插入仍从堆尾沿双亲链上浮；删除堆顶后，从至多 \(m\) 个孩子中选最优者再下沉。堆高为 \(O(\log_m n)\)，在 \(m\) 视为常数时插入、删除均为 \(O(\log_m n)\)。
⚠️ 增大 \(m\) 会降低高度，但每次下沉要比较更多孩子，不能只看树高断言一定更快。
b_373_8；PDF 第 373 页 · b_373_9；PDF 第 373 页 · b_373_14；PDF 第 373 页 · b_373_15怎样在单链表上用选择思想原地排序？（8.4 综合 05）¶
每趟扫描未排序链表，找出最大结点及其前驱，将它摘下并头插到结果链表。因为依次取出的是从大到小的元素，而头插会反转取出次序，最终结果为递增链表。
需特别处理最大结点恰为原链表首结点的情况。总共扫描 \(n+(n-1)+\cdots+1\) 个结点，时间 \(O(n^2)\)；只改指针，额外空间 \(O(1)\)。
b_373_16；PDF 第 373 页 · b_373_17；PDF 第 373 页 · b_373_18；PDF 第 374 页 · b_374_0怎样在线性时间内判断一个数组是否为小根堆？（8.4 综合 06）¶
只需扫描所有分支结点。对每个下标 \(i\)，检查 \(A[i]\le A[2i]\)；若右孩子存在，再检查 \(A[i]\le A[2i+1]\)。任一失败即返回假，全部通过返回真。
扫描范围是 \(1\sim\lfloor n/2\rfloor\)，时间 \(O(n)\)、空间 \(O(1)\)。当最后一个分支结点只有左孩子时，不能越界读取右孩子。
b_374_1；PDF 第 374 页 · b_374_2；PDF 第 374 页 · b_374_3优先队列为什么适合用堆，入队和出队怎样实现？（8.4 综合 07）¶
若“优先级最高者先出队”，固定容量时可用顺序存储的大根堆：数组保存元素，size 保存当前长度。
- 入队：放到
A[++size]，沿双亲链向上调整。 - 出队：保存根，用堆尾覆盖根，
size--，再向下调整并返回原根。 - 复杂度：取队头 \(O(1)\)，入队和出队均为 \(O(\log n)\)。
若数值越小优先级越高，则改用小根堆；结构和算法完全对称。
b_374_4；PDF 第 374 页 · b_374_5；PDF 第 374 页 · b_374_6；PDF 第 374 页 · b_374_7；PDF 第 374 页 · b_374_8；PDF 第 374 页 · b_374_9；PDF 第 374 页 · b_374_10；PDF 第 375 页 · b_375_0n 很大而只找最小 10 个数，怎样把比较次数压到线性量级？（2022 统考综合）¶
维护一个容量固定为 10 的大根堆：先用前 10 个数建堆；之后扫描每个 \(x\)，若 \(x\ge\) 堆顶就丢弃，若 \(x<\) 堆顶就替换堆顶并向下调整。扫描结束后，堆中就是最小的 10 个数。
因堆大小恒为 10，每个后续元素至多做 \(O(\log 10)\) 次比较，总时间 \(O(n)\)；10 个堆单元不随 \(n\) 增长，按渐进口径额外空间 \(O(1)\)。
⚠️ 求“最小 \(k\) 个”维护的是大根堆，使当前候选中的最大者最容易被淘汰。
b_375_1；PDF 第 375 页 · b_375_2；PDF 第 375 页 · b_375_3；PDF 第 375 页 · b_375_4；PDF 第 375 页 · b_375_5两个递增单链表怎样原地合并成递减链表？（2013 统考）¶
同时扫描两个表，每次摘下当前较小的结点，采用头插法接到结果表。扫描次序是从小到大，头插后整体次序恰好反转为从大到小；某一表耗尽后，继续把另一表的剩余结点逐个头插。
整个过程只改链，不创建数据结点，时间为 \(O(m+n)\)（也可写成 \(O(\max(m,n))\) 的同阶形式），额外空间 \(O(1)\)。2013 第 15 题选 D。
⚠️ 若用尾插法，得到的仍是递增表；题目要求递减正是选择头插的原因。
b_383_6；PDF 第 383 页 · b_383_7基数排序的某一趟结果、稳定性和初态无关性怎样判断？（2013、2015、2021 统考）¶
最低位优先法（LSD）从低位到高位，每一趟按当前位做稳定的分配与收集。判断中间状态时，只看“截至当前位组成的低位关键字”是否有序，并检查上一趟的相对次序是否被稳定保留。
- 2013 第 16 题：按个位、十位完成第二趟后选 C。
- 2015 第 17 题：分配和收集次数由位数和基数决定，元素移动次数与初态无关，选 C。
- 2021 第 18 题：第一趟只看个位，372 的相邻记录为 301、892，选 C。
复杂度为 \(O(d(n+r))\)，其中 \(d\) 是位数、\(r\) 是基数；它不是基于关键字两两比较的排序。
b_383_8；PDF 第 383 页 · b_383_9；PDF 第 383 页 · b_383_10；PDF 第 383 页 · b_383_11；PDF 第 383 页 · b_383_12；PDF 第 383 页 · b_383_13“归并”到底要求什么，比较次数怎样逐段累计？（2022、2024 统考）¶
归并是把两个或多个已有序子序列合成一个新的有序序列，并不等同于任意两段重新排序。2022 第 19 题选 A。
手算比较次数时，每次从各段首元素中选较小者；一段耗尽后，另一段剩余元素直接复制，不再比较。2024 第 20 题对给定三组序列逐组模拟，共比较 5 次，选 C。
💡 两个长度为 \(m,n\) 的有序段，最多比较 \(m+n-1\) 次；若一段整体小于另一段，最少只需 \(\min(m,n)\) 次。
b_383_14；PDF 第 383 页 · b_383_15；PDF 第 384 页 · b_384_0；PDF 第 384 页 · b_384_1；PDF 第 384 页 · b_384_2非递归二路归并怎样确定趟数并写出每趟序列？（8.5 综合 01）¶
令有序段长度 len 从 1 开始，每趟把相邻两个长度至多为 len 的段归并，然后令 len*=2。\(n=10\) 时需要
趟，段长依次由 1 变成 2、4、8、至少 10。
最后不足一个完整段或只有一个尾段时，按实际长度处理，不能丢掉。写中间结果时先画段界，再逐对归并，可避免把不同归并组交叉比较。
b_384_4；PDF 第 384 页 · b_384_5怎样按 LSD 法完整写出两趟基数排序？（8.5 综合 02）¶
先按个位把记录稳定地放入 \(0\sim9\) 号桶，再按桶号依次收集；第二趟按十位重复。每一桶必须保持进入顺序，否则下一高位无法在相等高位内保留低位次序。
若关键字位数不足，应在高位补 0 后再分配。手算核验：第一趟结束后个位非递减；第二趟结束后由“十位优先、个位次优”构成整体非递减序列。
b_384_6；PDF 第 384 页 · b_384_7；PDF 第 384 页 · b_384_8；PDF 第 384 页 · b_384_9比较计数排序怎样得到结果，它为什么可能不稳定，如何修改？（2021 统考综合）¶
对每一对元素只比较一次，并按程序的大小关系与平局规则给其中一个元素的计数加 1；最终 count[i] 是该记录在这套规则下的目标下标。关键字互异时，它等于严格小于该元素的元素数；有重复值时还包含程序规定的平局次序。题中输出为
比较次数固定为 \(n(n-1)/2\)，时间 \(O(n^2)\)，辅助数组空间 \(O(n)\)。
原程序遇到相等元素时会给较早元素加计数，可能把相等元素次序颠倒。要保持稳定，可令较后元素在相等时加计数，例如把判断改成：若 A[i] <= A[j] 则 count[j]++，否则 count[i]++。
b_384_10；PDF 第 384 页 · b_384_11；PDF 第 384 页 · b_384_12；PDF 第 385 页 · b_385_0；PDF 第 385 页 · b_385_1；PDF 第 385 页 · b_385_2；PDF 第 385 页 · b_385_3怎样从第二趟或中间表的“指纹”反推排序算法？（2009、2010、2025 统考）¶
先找算法特有的不变量：
- 插入排序：前 \(i+1\) 个元素局部有序；
- 冒泡排序：一端形成全局有序区，每趟至少固定一个极值；
- 希尔排序：存在某个增量 \(d>1\)，各同余子表分别有序；
- 选择/堆排序：一端极值区逐步扩大，但前部不必局部有序。
据此，2009 第 13 题第二趟只可能是插入排序，选 B；2010 第 14 题表现为冒泡，选 A；2025 第 23 题的间隔有序特征属于希尔排序，选 A。
b_390_6；PDF 第 390 页 · b_390_7；PDF 第 390 页 · b_390_8；PDF 第 390 页 · b_390_9；PDF 第 391 页 · b_391_9；PDF 第 391 页 · b_391_10哪些排序能保证每趟至少一个元素到最终位置？（2012 统考）¶
保证这一性质的典型算法有：
- 冒泡排序：每趟把一个极值冒到端点；
- 简单选择排序：每趟把一个极值放到有序区边界；
- 堆排序：每次输出堆顶并放到最终区；
- 快速排序：每趟划分使枢轴归位。
插入、希尔、归并和基数排序的中间趟不保证某个元素已经处在全局最终位置。2012 第 15 题中简单选择、快速、堆均满足，选 A。
b_390_10；PDF 第 390 页 · b_390_11大规模数据、链式存储等条件怎样影响归并、插入、希尔和堆的选择？（2017 统考）¶
- 2017 第 16 题：在题设算法都能完成任务时，选择归并而非插入的决定性理由是前者运行效率更高，选 B；不能笼统说归并“更省空间”或“一定更易实现”。
- 2017 第 17 题：顺序表改成链表后，希尔排序的跨距定位和堆排序的父子下标定位都失去优势，效率会明显降低，选 D。
归并排序反而较适合链表：合并时可改链而不移动大量元素；直接插入也能在链表上做，但定位仍需顺序扫描。
b_390_12；PDF 第 390 页 · b_390_13；PDF 第 390 页 · b_390_14；PDF 第 390 页 · b_390_15选择排序算法时，规模、初态、空间和稳定性怎样一起权衡？（2019、2020、2022 统考）¶
2019 第 18 题提醒要同时看数据规模、存储结构、稳定性要求和初始状态，四项均应考虑，选 D。
- 基本有序：直接插入比较和移动显著减少。2020 第 19 题中它快于简单选择，原因是比较次数更少，选 A。
- 元素少且基本有序：直接插入具有 \(O(1)\) 空间、稳定、常数开销小等优势。2022 第 20 题四项理由均成立，选 D。
⚠️ 不能只背平均复杂度；输入特征、额外空间和稳定性常会改变最优选择。
b_390_16；PDF 第 390 页 · b_390_17；PDF 第 390 页 · b_390_18；PDF 第 390 页 · b_390_19；PDF 第 391 页 · b_391_0；PDF 第 391 页 · b_391_1；PDF 第 391 页 · b_391_2；PDF 第 391 页 · b_391_3；PDF 第 391 页 · b_391_4怎样同时判断排序稳定性与最坏元素移动次数？（2023、2025 统考）¶
稳定性要看相等关键字能否跨越换序：直接插入、冒泡、归并、基数稳定；希尔、快速、简单选择、堆排序不稳定。2023 第 21 题选 C。
若只比较最坏元素移动次数，简单选择每趟至多交换一次，总移动为 \(O(n)\)；插入、冒泡在最坏情况下需 \(O(n^2)\) 次移动，快排也可能大量交换。因此 2025 第 22 题选 D。
💡 “比较次数少”和“移动次数少”是两项指标；简单选择比较固定为 \(n(n-1)/2\)，但移动很少。
b_391_5；PDF 第 391 页 · b_391_6；PDF 第 391 页 · b_391_7；PDF 第 391 页 · b_391_8一个序列排序所需的最少交换次数怎样求？（8.6 综合 01）¶
若允许每次交换任意两个位置，最少交换次数可由“当前位置到目标位置”的置换环求得：一个长度为 \(L\) 的环需要 \(L-1\) 次交换，总数为
对题给序列 \(\{3,7,6,9,7,1,4,5,20\}\)，按答案所采用的目标次序处理重复关键字，最少交换 5 次。
⚠️ 有重复元素时，先合理匹配相等元素的目标位置，选择能增加置换环数的匹配，不能机械按某一种标签化次序计算。
b_391_11；PDF 第 391 页 · b_391_12；PDF 第 391 页 · b_391_13数组前 m 个和后 n 个元素各自有序，怎样原地合成整体有序？（8.6 综合 02）¶
王道答案的原地做法是从后半段首元素开始做直接插入：对 \(i=m+1\sim m+n\)，保存 \(A[i]\)，在前面有序区从后向前移动较大元素，再插入。时间最坏 \(O(mn)\)，空间 \(O(1)\)。
若允许 \(O(m+n)\) 辅助空间，则像归并排序一样用两个指针线性合并，时间 \(O(m+n)\)。考试答题要服从题目空间要求：未要求原地时可给线性归并；要求 \(O(1)\) 空间时采用书中插入法。
b_391_14；PDF 第 391 页 · b_391_15；PDF 第 391 页 · b_391_16；PDF 第 391 页 · b_391_17；PDF 第 392 页 · b_392_0；PDF 第 392 页 · b_392_1怎样用不超过 n 次比较把 K_n 放到排序后的最终位置？（8.6 综合 03）¶
把 \(K_n\) 当作枢轴做一趟划分即可：从左向右扫描其余 \(n-1\) 个元素，把小于等于枢轴的放左侧、大于枢轴的放右侧，最后把枢轴交换到两区边界。
每个其他关键字只需与 \(K_n\) 比较一次，共 \(n-1\) 次，不超过 \(n\)；完成后只保证 \(K_n\) 归位和左右分区关系，不要求两侧内部有序。
b_392_2；PDF 第 392 页 · b_392_3；PDF 第 392 页 · b_392_4k 路最佳归并树为什么要补虚段，WPL 怎样计算？（2013、2019 统考）¶
严格 \(k\) 叉归并树只有度为 0 和 \(k\) 的结点，叶数 \(m'\) 必须满足
不满足时补权值为 0 的虚段，再每次合并最小的 \(k\) 个权值。
- 2013 第 13 题：三叉、6 个实段，补 1 个 0；依次合并 \((0,2,3)\to5\)、\((4,5,5)\to14\)、\((6,7,14)\to27\)，WPL 为 46，选 B。
- 2019 第 15 题：12 路、120 段，需补 2 个虚段，选 B。
补的是“长度为 0 的初始归并段”，目的不是改变数据，而是让归并树成为严格 \(k\) 叉树。
b_399_22；PDF 第 399 页 · b_399_23；PDF 第 400 页 · b_400_0；PDF 第 400 页 · b_400_1；PDF 第 400 页 · b_400_2；PDF 第 400 页 · b_400_3；PDF 第 400 页 · b_400_4；PDF 第 400 页 · b_400_5；PDF 第 400 页 · b_400_6；PDF 第 400 页 · b_400_10；PDF 第 400 页 · b_400_11；PDF 第 400 页 · b_400_1210TB 级文件为什么必须采用外部排序？（2016 统考）¶
当待排文件远大于内存时，不能把全部记录一次装入内存。应先分批读入、内部排序生成若干初始归并段，再进行多路归并，最终形成有序文件。2016 第 14 题选 D。
外部排序的主要代价是磁盘 I/O，而不是内存中的比较；优化方向因此是减少初始归并段数、减少归并趟数和降低加权读写量。
b_400_8；PDF 第 400 页 · b_400_9败者树的冠军结点保存什么，为什么适合多路归并？（2024 统考）¶
败者树的内部结点记录每次比较的败者，根上方的冠军位置保存当前最小关键字所属的归并段号。输出冠军后，只需用该段的新首记录沿原路径重新比赛。
2024 第 16 题中冠军结点保存最小关键字所在段的段号，选 D。一次调整只比较 \(O(\log k)\) 次，而且每层一次比较，避免普通堆下沉时先比较孩子再与父结点比较的额外开销。
b_400_13；PDF 第 400 页 · b_400_1480 个初始归并段在趟数或文件数受限时，归并路数怎样反推？（8.7 综合 01）¶
平衡 \(k\) 路归并的趟数为 \(s=\lceil\log_k r\rceil\)，其中 \(r\) 为初始归并段数。
- 要在 3 趟内归并 80 段：\(k^3\ge80\)，最小 \(k=5\)。
- 若磁盘上最多允许 15 个文件，轮换使用时可做 14 路归并，因还需 1 个输出文件；\(\lceil\log_{14}80\rceil=2\)。
- 若限定 2 趟，需 \(k^2\ge80\)，最小 \(k=9\)。
先由限制确定 \(k\) 或 \(s\)，再用幂次不等式核验，避免把对数向下取整。
b_400_15；PDF 第 400 页 · b_400_16；PDF 第 400 页 · b_400_17；PDF 第 400 页 · b_400_18已知记录数、块长和内存容量，怎样算初始段数、归并路数与 I/O？（8.7 综合 02）¶
题中 4500 个记录，每块 75 个记录，共 60 块；内存可装 450 个记录，即 6 块。
- 每个初始归并段含 450 个记录，共 \(4500/450=10\) 段，每段 6 块。
- 多路归并需 1 个输出缓冲区，因此最多 \(6-1=5\) 路。
- 10 段做 5 路归并需 \(\lceil\log_5 10\rceil=2\) 趟。
- 每趟读取 60 块并写回 60 块，即每趟 120 次块 I/O；两趟共 240 次。
若题目还计“生成初始归并段”的读写，则应另加一次全文件读和写；答题前先看统计范围。
b_401_0；PDF 第 401 页 · b_401_1；PDF 第 401 页 · b_401_2；PDF 第 401 页 · b_401_3；PDF 第 401 页 · b_401_4怎样手工模拟六路败者树连续选出前五个记录？（8.7 综合 03）¶
先取六个归并段的当前首记录比赛，输出最小者；只从获胜段读入下一个记录，并沿该叶到根的路径重赛，其他段当前记录不变。
题给六段首部依次推进，前五个输出为
每输出一个记录只更新一条高为 \(\lceil\log_2 6\rceil\) 的路径。遇到相等关键字时按题设或既定段号规则打破平局，以保持可重复的归并顺序。
b_401_5；PDF 第 401 页 · b_401_6；PDF 第 401 页 · b_401_7四路最佳归并树怎样补虚段并求最少 I/O 代价？（8.7 综合 04）¶
12 个实归并段做四路最佳归并，因 \((12-1)\bmod3=2\)，需补 1 个权为 0 的虚段，使叶数变为 13。随后仿照哈夫曼算法，每次取 4 个最小权值合并，把新权值重新放回候选集合。
所有内部结点权值之和即带权路径长度，也就是每条记录参与归并的累计次数；本题最小 WPL 为 690。若把一次读和一次写都计为 I/O，总记录读写量为 \(2\times690\)。
b_401_8；PDF 第 401 页 · b_401_9；PDF 第 401 页 · b_401_10；PDF 第 401 页 · b_401_11；PDF 第 402 页 · b_402_0置换—选择排序怎样生成不等长初始归并段？（2023 统考综合）¶
工作区容量为 4。反复输出当前工作区中“不小于本段最近输出值”的最小记录，再从输入补入一个记录；新记录若小于最近输出值，就冻结到下一段。当前段无可选记录时结束该段，解冻后开始下一段。
题给输入得到三段：
第一段最小长度可为工作区容量 \(m\)，最大可达全部 \(n\) 个记录；长度由输入次序决定，平均约为传统等长段的 2 倍。
b_402_1；PDF 第 402 页 · b_402_2；PDF 第 402 页 · b_402_3；PDF 第 402 页 · b_402_4【原书归纳总结与思维拓展】第8章¶
怎样用“相等元素能否换序”严格判断排序稳定性？¶
稳定性只讨论关键字相等的不同记录在排序前后的相对次序。证明稳定，要说明所有移动都不会让相等记录互相跨越；证明不稳定，只需构造一个最小反例，使两个相等记录被交换或跨越。
- 稳定：直接插入、折半插入、冒泡、归并、基数排序。
- 不稳定：希尔、快速、简单选择、堆排序。
稳定与算法优劣无必然关系；“内部/外部排序”按数据是否能全部装入内存区分，也不是按算法是否稳定区分。
b_344_3；PDF 第 344 页 · b_344_4；PDF 第 345 页 · b_345_1；PDF 第 345 页 · b_345_2；PDF 第 345 页 · b_345_3；PDF 第 345 页 · b_345_4怎样用四类不变量识别一道排序中间过程题？¶
先不逐个试算法，而是按中间状态找不变量：
- 有序前缀：插入排序前 \(i+1\) 项局部有序。
- 端部最终区：冒泡、简单选择、堆排序每趟让端部至少增加一个最终元素。
- 枢轴分区：快排出现“左块 \(\le\) 枢轴 \(\le\) 右块”，但块内可乱。
- 等距子表有序：希尔排序按某个增量的同余组有序。
归并则表现为等长有序段逐趟翻倍；基数排序表现为当前已处理数位上的稳定有序。
b_350_8；PDF 第 350 页 · b_350_9；PDF 第 350 页 · b_350_10；PDF 第 350 页 · b_350_11快速排序的好坏为什么本质上是递归树的平衡问题？¶
每次枢轴若把子表近似均分，递归树高约为 \(\log_2 n\)，每层处理总量 \(O(n)\)，总时间 \(O(n\log n)\)；若枢轴总是最小或最大值，树退化为高度 \(n\) 的单链，总时间 \(O(n^2)\)、递归栈 \(O(n)\)。
因此已有序输入并非天然“容易”：若固定取首/尾元素为枢轴，它反而可能触发最坏情况。随机选枢轴或三者取中是降低退化概率的工程改进。
b_359_7；PDF 第 359 页 · b_359_8；PDF 第 359 页 · b_359_13；PDF 第 359 页 · b_359_14建堆、插入、删除和完整堆排序的复杂度为什么不同？¶
- 自底向上建堆：从 \(\lfloor n/2\rfloor\) 反向下调，总代价 \(O(n)\)。
- 插入：堆尾加入后上调，最坏 \(O(\log n)\)。
- 删除堆顶：堆尾补根后下调，最坏 \(O(\log n)\)。
- 堆排序：建堆 \(O(n)\)，再做 \(n-1\) 次删除式调整，总时间始终 \(O(n\log n)\)、额外空间 \(O(1)\)。
不能把“逐个插入建堆”的 \(O(n\log n)\) 与“自底向上建堆”的 \(O(n)\) 混用。
b_369_17；PDF 第 369 页 · b_369_18；PDF 第 369 页 · b_369_19；PDF 第 369 页 · b_369_20；PDF 第 370 页 · b_370_0；PDF 第 370 页 · b_370_1归并趟数、两个有序段的比较上下界怎样一眼算出？¶
\(n\) 个单元素段做 \(k\) 路平衡归并，趟数为 \(\lceil\log_k n\rceil\)。两个长度为 \(m,n\) 的有序段合并：
- 最多比较 \(m+n-1\) 次，发生在两段元素交替出现时；
- 最少比较 \(\min(m,n)\) 次，发生在较短段整体先耗尽时；
- 无论初态如何，归并总时间量级仍为 \(O(m+n)\)。
“趟数固定”不代表每次比较次数完全相同；它只说明分段层数由规模与归并路数决定。
b_382_11；PDF 第 382 页 · b_382_12；PDF 第 382 页 · b_382_13；PDF 第 382 页 · b_382_14；PDF 第 382 页 · b_382_15；PDF 第 382 页 · b_382_16排序算法选择时，怎样按硬约束逐层排除？¶
建议按顺序问：
- 数据能否全部进内存？不能则进入外部排序。
- 是否必须稳定？若是，先排除希尔、快排、选择、堆。
- 额外空间是否严格受限？\(O(1)\) 时优先插入、希尔、堆等原地算法。
- 数据是否小或基本有序？是则直接插入常最合适。
- 是否规模大且追求稳定的 \(O(n\log n)\)？可选归并；若强调原地且最坏界，选堆。
选择结论必须对应题目给出的硬条件，不能只按平均时间复杂度排名。
b_389_13；PDF 第 389 页 · b_389_14；PDF 第 389 页 · b_389_15；PDF 第 389 页 · b_389_16外部排序的归并趟数和读写代价怎样统一建模？¶
设有 \(r\) 个初始归并段，采用 \(k\) 路平衡归并，则归并趟数
若文件共 \(N\) 个记录，每趟都完整读一遍、写一遍，平衡归并阶段约需 \(2Ns\) 次记录 I/O；若各段长度不等，则用归并树 WPL 计算更准确的累计参与次数。
增加 \(k\) 能减少趟数，但需要 \(k\) 个输入缓冲区、1 个输出缓冲区，并增加选择当前最小段首的成本；败者树把这一选择降为 \(O(\log k)\)。
b_399_2；PDF 第 399 页 · b_399_3；PDF 第 399 页 · b_399_4；PDF 第 399 页 · b_399_5；PDF 第 399 页 · b_399_6；PDF 第 399 页 · b_399_7；PDF 第 399 页 · b_399_8；PDF 第 399 页 · b_399_9整数范围固定时，怎样做到线性时间且按渐进口径为常数空间？¶
若整数只来自固定范围 \(0\sim65535\)，可建立固定大小的计数数组 count：扫描输入做 count[x]++，再按下标从小到大输出。时间为 \(O(n+65536)=O(n)\)；当取值范围被视为固定常数时，空间为 \(O(1)\)。
若有负数，可整体加固定偏移映射到非负下标。⚠️ 若值域大小随 \(n\) 增长，则空间应写成 \(O(r)\)，不能仍称 \(O(1)\)；这个结论依赖“值域固定”的前提。
b_403_6；PDF 第 403 页 · b_403_7；PDF 第 403 页 · b_403_8；PDF 第 403 页 · b_403_9实际高效排序为什么常把多种算法混合使用？¶
单一算法在所有规模和输入上都不占优。常见混合策略是：大区间用快速排序或归并排序，递归到底层的小区间后切换为直接插入排序，减少函数调用和小规模常数开销；快排还可用三者取中、随机枢轴或深度阈值避免极端退化。
工程选型仍要回到四个条件：数据规模、内存限制、稳定性要求、输入初态。考试答题以教材给定算法与复杂度为主，混合策略用于理解“为什么实际库函数与纯教材算法不完全相同”。
b_403_1；PDF 第 403 页 · b_403_2；PDF 第 403 页 · b_403_3；PDF 第 403 页 · b_403_4；PDF 第 403 页 · b_403_5【易混点】第8章成对概念对照¶
| 概念 A | 概念 B | 一句话切分 |
|---|---|---|
| 内部排序 | 外部排序 | 全在内存 vs 需内外存多次交换，瓶颈是 I/O |
| 直接插入 | 折半插入 | 边比边搬 vs 先折半定位再统一搬；⚠️ 只省比较不省移动 |
| 直接插入 | 希尔 | 稳定、可用链表 vs 不稳定、只能顺序存储 |
| 冒泡的有序 | 插入的有序 | ⚠️ 全局有序（每趟定死一个） vs 局部有序 |
| 冒泡 | 快排 | 稳定、可链式 vs 不稳定；本书考试按顺序存储归类，工程可另写链式变体 |
| 简单选择 | 堆排序 | 比较次数恒 n(n−1)/2 vs 建堆 O(n) + n−1 次 O(log₂n) |
| 堆插入 | 堆删除调整 | 自下而上（上浮） vs 自上而下（下沉） |
| 建堆起点 | — | ⚠️ 从 ⌊n/2⌋ 到 1，自底向上地做自上而下筛选 |
| Top-K 求最大 | 求最小 | 用小顶堆 vs 用大顶堆 |
| 归并 | 快排 | 稳定、O(n) 空间、三种情况都 O(nlogn) vs 不稳定、O(log₂n) 空间、最坏 O(n²) |
| 基数排序 | 计数排序 | 按位分配收集，O(d(n+r)) vs 按值计数累加，O(n+k) |
| MSD | LSD | 最高位优先 vs 最低位优先（常用） |
| 增大 k | 减少 r | 多路归并 + 败者树 vs 置换-选择排序 |
| 败者树 | 普通多路归并 | 比较次数与 k 无关 vs 每次选最小要 k−1 次比较 |
| 普通归并树 | 最佳归并树 | WPL 大 vs 哈夫曼思想，小段先并 |
【必背数字】第8章¶
| 数字 | 含义 |
|---|---|
| n²/4 | 直接插入排序平均比较/移动次数 |
| n(n−1)/2 / 3n(n−1)/2 | 冒泡最坏比较次数 / 移动次数（每次交换 3 次移动） |
| O(n^1.3) | 希尔排序在常见 n 下的时间复杂度 |
| n(n−1)/2 / 3(n−1) | 简单选择的比较次数（恒定）/ 最多移动次数 |
| ⌊n/2⌋ | 建堆的起始结点编号 |
| 4n | 建堆时关键字总比较次数的上界 → 建堆 O(n) |
| O(n log₂k) / O(k) | Top-K 问题的时间 / 空间复杂度 |
| ⌈log₂n⌉ / ⌈n/(2h)⌉ | 归并总趟数 / 每趟调用 Merge 的次数 |
| ⌈log_k N⌉ | k 路归并的趟数 |
| O(d(n+r)) / O(r) | 基数排序时间 / 空间 |
| 128 → 96 | 教材算例 2 路 → 4 路归并的 I/O 次数 |
| ⌈log₂k⌉ + 1 | k 路归并败者树的深度 |
| (n−1)⌈log₂r⌉ | 用败者树后的总比较次数（与 k 无关） |
| 2 × WPL | 最佳归并树的总 I/O 次数 |
| (n₀−1)%(k−1) = u ≠ 0 → 补 k−u−1 个虚段 | 虚段判定 |
| 484 / 446 / 386 / 326 | 教材最佳归并树四个方案的 I/O 次数 |
【解题路线】第8章：给中间结果反推是哪种排序¶
⚠️ 这是排序选择题最主要的题型，按下面的特征逐条对： - 两端或某端已有若干元素在最终位置，且是最大/最小的那几个 → 冒泡、简单选择、堆排序 - 再细分：⚠️ 堆排序每趟把堆顶换到末尾，前面部分仍是堆的形态（不是有序） - 某个元素左边全比它小、右边全比它大，但两边内部还乱 → ⚠️ 快速排序一趟划分 - 前面一段有序，但这些元素未必在最终位置，后面部分原封未动 → ⚠️ 直接插入排序 - 序列被切成若干等长的有序段（段长 1→2→4→8） → 归并排序 - 整体按某一位（个位/十位）有序 → 基数排序 - 相隔一定距离的元素被换到位，整体"大致有序"但无段有序特征 → 希尔排序
确认完算法后，剩下三问（时间/空间/稳定性）直接查 【口诀速记】排序算法三维口诀表。
⚠️ 两个反直觉点单独记：简单选择排序的比较次数与初态无关；在本书固定取子表端点为枢轴的实现中，初始基本有序常导致最坏划分，但随机/三数取中时不可照搬。
b_343_5；PDF 第 343 页 · b_343_6