排序

考点定位

所属大纲章节：排序的基本概念；直接插入排序、折半插入排序、冒泡排序、简单选择排序、希尔排序、快速排序、堆排序、二路归并排序、基数排序；外部排序；排序算法的分析和应用
常见题型：选择题（复杂度对比、稳定性判断、给每趟中间结果反推排序算法、堆性质）；手推大题（快排一趟划分、自底向上建堆、归并过程）；外部排序计算（败者树比较次数、最佳归并树 WPL）
考查频率：极高。"每趟结果→判断算法"是 408 数据结构的招牌题型，几乎年年出现

工程直觉迁移：qsort/std::sort 你调了半辈子，工程直觉知道"快排平均最快、可配比较器"。本章要补的是考试特有产物：各算法每趟之后序列的可判定特征、最好/最坏情形与枢轴选取的耦合、建堆 $O(n)$ 的推导、以及外部排序（败者树/置换选择/最佳归并树）——后者工程里几乎不手碰，全是应试账。

前置知识：绪论与复杂度分析（递归方程解法）、树与二叉树（完全二叉树编号性质，堆排序用）、查找（折半查找，折半插入用）。

零、排序的基本概念

稳定性：待排序序列中存在关键字相同的多个记录，排序后它们的相对次序不变，则算法稳定。注意两点：① 稳定性由算法本身决定，对任何输入成立才算稳定，不能只看某一次运行；② 考试判定稳定性用最小反例验证（见各节）。
内部排序 vs 外部排序：排序期间数据全部在内存为内部排序；数据量大于内存、排序期间需内外存交换为外部排序（第八节）。内部排序按思路分四族：插入、交换、选择、归并（基数排序是基于分配收集的非比较排序，单列）。
约定：以下序列下标从 1 开始，均为升序排序，移动/比较次数均按"关键字比较、元素移动"两个口径分别给出。

一、插入排序

直接插入排序

思想：把序列分为前部有序区 + 后部无序区，每次把无序区第一个元素从后向前扫描插入有序区的正确位置——就是你打扑克理牌的动作。

步骤（第 i 趟，i = 2..n）：

暂存 r[0] = r[i]（r[0] 兼作哨兵，防止下标越界，同顺序查找的哨兵）；
从 j = i - 1 起向前，只要 r[j] > r[0] 就 r[j+1] = r[j]（后移）；
遇到 r[j] <= r[0] 或 j 到 0 时停止，r[j+1] = r[0]。

void InsertSort(int r[], int n) {          // r[0] 为哨兵，r[1..n] 存数据
    for (int i = 2; i <= n; i++) {
        if (r[i] < r[i-1]) {               // 已有序则跳过，保证最好情形
            r[0] = r[i];
            int j;
            for (j = i - 1; r[0] < r[j]; j--)
                r[j+1] = r[j];             // 边比较边后移
            r[j+1] = r[0];
        }
    }
}

复杂度推导：第 i 趟最坏比较 $i$ 次（与前面 $i-1$ 个元素及哨兵各一次）、移动 $i+1$ 次（暂存、 $i-1$ 次后移、归位）。求和：

$\text{最坏（逆序）}：\text{比较} \sum_{i=2}^{n} i = \frac{(n+1)(n-1)}{2},\quad \text{移动} \sum_{i=2}^{n}(i+1) = \frac{(n+2)(n-1)}{2}$

即 $O(n^2)$ 。最好（正序）：每趟比较 1 次、移动 0 次，共 $n-1$ 次比较， $O(n)$ 。平均（每个元素等概率插入到一半位置）比较与移动各约 $n^2/4$ ，仍 $O(n^2)$ 。空间 $O(1)$ （哨兵），稳定（相等时不越过、停在等值元素之后）。

适用：序列基本有序或 n 较小时最优选——这也是希尔排序与快排小区间退化的理论依据。

折半插入排序

直接插入的"边比较边后移"改为先用折半查找定位插入点，再一次性后移（比较与移动解耦）：

在有序区 r[1..i-1] 上折半查找 r[i] 的插入位置（找第一个大于 r[i] 的位置，保证稳定）；
该位置之后的元素整体后移一位，放入 r[i]。

复杂度：比较次数降为 $\sum_{i=2}^{n} \lceil \log_2 i \rceil = O(n\log_2 n)$ ；但移动次数不变（仍 $O(n^2)$ ，后移与比较多少无关），故总时间仍 $O(n^2)$ 。稳定，空间 $O(1)$ 。考点：折半插入只减少比较、不减移动，时间复杂度量级不变。

希尔排序（缩小增量排序）

思想：按增量 $d$ 把序列分成 $d$ 组（下标相差 $d$ 的同组），组内直接插入排序；逐步缩小 $d$ （要求各增量互质、最后一个增量必须是 1），最终 $d=1$ 时全序列基本有序，再来一次直接插入即完成——利用"直接插入在基本有序序列上接近 $O(n)$ "的特性。

以 {49, 38, 65, 97, 76, 13, 27, 50}（模拟题，待动画化）为例，增量序列取 4、2、1：

趟	增量 d	分组（下标 1..8）	组内排序后全序列
1	4	{49,76}、{38,13}、{65,27}、{97,50}	49, 13, 27, 50, 76, 38, 65, 97
2	2	{49,27,76,65}、{13,50,38,97}	27, 13, 49, 38, 65, 50, 76, 97
3	1	全序列一组	13, 27, 38, 49, 50, 65, 76, 97

复杂度：依赖增量序列，无法给出统一的精确数学分析；经验上约 $O(n^{1.3})$ ，好于 $O(n^2)$ 、差于 $O(n\log_2 n)$ 。空间 $O(1)$ 。不稳定（相同关键字可能被增量分组拆到不同组，跨组交换打乱相对次序；且组内跳跃式插入也保证不了）。希尔排序是第一个突破 $O(n^2)$ 的排序算法——历史地位是选择题点。

二、交换排序

冒泡排序

步骤：n 个元素做最多 $n-1$ 趟；每趟从前往后两两比较相邻元素，逆序则交换，一趟结束时当前无序区最大元素"沉"到末尾；若某一趟未发生交换，说明已有序，提前终止。

void BubbleSort(int r[], int n) {
    for (int i = 1; i < n; i++) {
        bool exchange = false;
        for (int j = 1; j <= n - i; j++)
            if (r[j] > r[j+1]) { swap(r[j], r[j+1]); exchange = true; }
        if (!exchange) return;             // 本趟无交换，已全局有序
    }
}

复杂度：最好（正序）比较 $n-1$ 次、移动 0 次， $O(n)$ ；最坏（逆序）比较 $\sum_{i=1}^{n-1}(n-i) = \frac{n(n-1)}{2}$ ，移动 3 倍于此（swap 三次赋值）， $O(n^2)$ ；平均 $O(n^2)$ 。空间 $O(1)$ ，稳定（相等不交换）。每趟至少一个元素到达最终位置（无序区末尾）。

快速排序（重点中的重点）

思想：分治。每趟在序列中选一个枢轴（pivot），通过一趟划分把序列分成"左边全部 ≤ 枢轴、右边全部 ≥ 枢轴"两块，枢轴落位；再对左右两块递归。

一趟划分过程（以首元素为枢轴、双向交替法，408 标准动作）：设枢轴 pivot = r[low]，low、high 为两端：

从 high 端向左扫描，找到第一个 < pivot 的元素，移到 low 端空位（low 处已保存到 pivot 变量，视为空）；
从 low 端向右扫描，找到第一个 > pivot 的元素，移到 high 端空位；
交替 1、2，low 与 high 相遇时，r[low] = pivot——枢轴落最终位置，一趟结束。

int Partition(int r[], int low, int high) {
    int pivot = r[low];                    // 暂存枢轴，r[low] 视为空位
    while (low < high) {
        while (low < high && r[high] >= pivot) high--;   // 右端找小者填左坑
        r[low] = r[high];
        while (low < high && r[low] <= pivot) low++;    // 左端找大者填右坑
        r[high] = r[low];
    }
    r[low] = pivot;                        // 枢轴落位，low == high
    return low;
}
void QuickSort(int r[], int low, int high) {
    if (low < high) {
        int pos = Partition(r, low, high);
        QuickSort(r, low, pos - 1);
        QuickSort(r, pos + 1, high);
    }
}

手推示范（模拟题，另配单步交互动画见交互演示）：{49, 38, 65, 97, 76, 13, 27, 50}，pivot = 49：

步	动作	序列状态（low, high）
1	high 端找 <49：50 否、27 是，填到 low	27, 38, 65, 97, 76, 13, 空, 50（low=1, high=8）
2	low 端找 >49：27、38 否，65 是，填到 high 空位	27, 38, 空, 97, 76, 13, 65, 50（low=3, high=8）
3	high 端向左找 <49：65、97、76 否，13 是	27, 38, 13, 97, 76, 空, 65, 50（low=3, high=6）
4	low 端找 >49：13 否，97 是	27, 38, 13, 空, 76, 97, 65, 50（low=4, high=6）
5	high 端找 <49：97、76、50 否，与 low 相遇	low = high = 4，pivot 归位

第一趟结果：{27, 38, 13, 49, 76, 97, 50, 65}——49 在位置 4（最终位置），左侧全部 < 49，右侧全部 > 49。

复杂度推导：

最好：每次枢轴恰好平分， $T(n) = 2T(n/2) + cn$ ，解得 $T(n) = O(n\log_2 n)$ （空间为递归深度 $\lfloor\log_2 n\rfloor + 1$ ，即 $O(\log_2 n)$ ）；
最坏：序列原本有序（正序或逆序）且取首/尾元素为枢轴——每趟划分极不对称（一侧空、另一侧 n−1 个）， $T(n) = T(n-1) + cn$ 退化为 $O(n^2)$ ，递归深度 $O(n)$ ；
平均： $O(n\log_2 n)$ ，且常数因子是所有 $O(n\log_2 n)$ 内部排序中最小的——"平均意义下最快的内部排序"。
空间：递归工作栈，最好/平均 $O(\log_2 n)$ ，最坏 $O(n)$ 。不稳定（划分时远程跳跃交换，反例：{3, 2, 2} 一趟后两个 2 的次序对调）。

关键考点：每趟结束后，至少有一个元素（枢轴）落在最终位置；反之，快排每趟并不保证"两个子区间内部有序"。枢轴选取可优化（三者取中等），使最坏情形难触发但不改变理论最坏。

三、选择排序

简单选择排序

步骤：n − 1 趟；第 i 趟从无序区 r[i..n] 中选出最小元素，与 r[i] 交换，有序区向前扩一格。

void SelectSort(int r[], int n) {
    for (int i = 1; i < n; i++) {
        int min = i;
        for (int j = i + 1; j <= n; j++)
            if (r[j] < r[min]) min = j;    // 只记录，不交换
        if (min != i) swap(r[i], r[min]);
    }
}

复杂度：比较次数与初始状态无关，恒为 $\sum_{i=1}^{n-1}(n-i) = \frac{n(n-1)}{2}$ ；移动最少 0 次（已有序）、最多 $3(n-1)$ 次。总 $O(n^2)$ ，空间 $O(1)$ 。不稳定——最小反例 {3, 3, 1}：第一趟 1 与第一个 3 交换，两个 3 相对次序颠倒。每趟至少一个元素（无序区最小者）就位。

堆排序

堆的定义：n 个元素的序列 {k₁, …, kₙ} 视为完全二叉树的顺序存储（编号 i 的孩子为 2i、2i+1，双亲为 ⌊i/2⌋），若满足 $k_i \ge k_{2i}$ 且 $k_i \ge k_{2i+1}$ （对存在的孩子）则称大顶堆（父不小于子）；全部取 ≤ 则为小顶堆。注意：堆只约束父子，兄弟、堂兄弟之间无序；堆顶（k₁）是全堆最大（大顶堆）或最小（小顶堆）。

向下调整（筛选，HeapAdjust）——堆排序的原子操作：设以 2i、2i+1 为根的子树已是大顶堆，但 kᵢ 可能小于孩子：

暂存 tmp = r[i]，从其较大的孩子开始比较；
若孩子大于 tmp，孩子上移一层，继续向下一层比较；
直到 tmp 不小于两个孩子或到叶，放入空位。单次调整 $O(\log_2 n)$ 。

自底向上建堆（堆排序第一步）：从最后一个分支结点 i = ⌊n/2⌋ 开始，倒序（⌊n/2⌋ 递减到 1）对每个结点做向下调整——保证每次调整时其左右子树已是堆。

void BuildMaxHeap(int r[], int n) {
    for (int i = n / 2; i >= 1; i--)       // 最后一个分支结点起，倒序
        HeapAdjust(r, i, n);
}
void HeapSort(int r[], int n) {
    BuildMaxHeap(r, n);
    for (int i = n; i > 1; i--) {
        swap(r[1], r[i]);                  // 堆顶(最大)与当前末位交换
        HeapAdjust(r, 1, i - 1);           // 剩余 i-1 个重新成堆
    }
}

手推示范（模拟题，待动画化）：{50, 36, 66, 90, 14, 22, 5, 18} 建大顶堆，n = 8，⌊8/2⌋ = 4 起：

步	调整结点	检查	结果序列
1	i=4（90）	孩子 18（位置 8）：90 ≥ 18，不动	50, 36, 66, 90, 14, 22, 5, 18
2	i=3（66）	孩子 22、5：66 最大，不动	同上
3	i=2（36）	孩子 90、14，最大者 90 > 36 → 交换；36 落位置 4，其孩子 18 < 36 止	50, 90, 66, 36, 14, 22, 5, 18
4	i=1（50）	孩子 90、66，最大者 90 > 50 → 交换；50 落位置 2，孩子 36、14 均 < 50 止	90, 50, 66, 36, 14, 22, 5, 18

建堆完成：{90, 50, 66, 36, 14, 22, 5, 18}。对应完全二叉树：

建堆为什么是 O(n) 而不是 O(n log n)：高度为 h 的结点至多 $\lceil n/2^{h+1} \rceil$ 个，每个结点调整代价正比于其高度 h（向下最多沉 h 层），总代价：

$\sum_{h=0}^{\lceil \log_2 n \rceil} \left\lceil \frac{n}{2^{h+1}} \right\rceil \cdot O(h) \le O(n) \cdot \sum_{h=0}^{\infty} \frac{h}{2^{h+1}} = O(n) \cdot 1 = O(n)$

（用 $\sum_{h\ge0} h/2^{h+1} = 1$ ；一半结点是叶子、根本不调整，这是"叶多干少"的红利。）排序阶段：n − 1 次"交换 + 下调"，每次 $O(\log_2 n)$ ，共 $O(n\log_2 n)$ 。总时间 $O(n\log_2 n)$ （最好 = 最坏 = 平均），空间 $O(1)$ ，不稳定（交换是远程的）。建堆 + 排序全程比较次数不超过 $O(n\log_2 n)$ ，适合只求前 k 大/小（Top-k：维护 k 元素的小顶堆，扫一遍 $O(n\log_2 k)$ ——工程与考试双热点）。

堆的插入：新元素放到堆尾（位置 n+1），向上调整（与双亲比较，大于双亲则上浮）直到根或不再大， $O(\log_2 n)$ 。删除堆顶：末尾元素补到堆顶，再向下调整， $O(\log_2 n)$ 。

大顶堆升序、小顶堆降序：升序要每次取当前最大放尾部，故升序用大顶堆；反之降序用小顶堆（问什么配什么，反着说必错）。

四、归并排序（二路归并）

Merge 操作：把两个相邻有序段 r[low..mid]、r[mid+1..high] 归并为一个有序段：借辅助数组 tmp，i、j、k 分别指向两段与 tmp 起点，反复取 r[i] ≤ r[j]（取等号保证稳定）的小者放入 tmp 并推进；一段耗尽后另一段整体复制；最后把 tmp 回拷到 r。

void Merge(int r[], int tmp[], int low, int mid, int high) {
    int i = low, j = mid + 1, k = low;
    while (i <= mid && j <= high)
        tmp[k++] = (r[i] <= r[j]) ? r[i++] : r[j++];   // = 保证稳定
    while (i <= mid)   tmp[k++] = r[i++];
    while (j <= high)  tmp[k++] = r[j++];
    for (k = low; k <= high; k++) r[k] = tmp[k];
}

递归版（自顶向下）：MergeSort(low, high)——mid 二分，先归并排两半，再 Merge。非递归版（自底向上）：归并段长度取 1, 2, 4, …, 每轮把相邻两段 Merge，长度翻倍，直到 ≥ n：

轮	段长	{49, 38, 65, 97, 76, 13, 27, 50} 的状态
初始	1	49 \| 38 \| 65 \| 97 \| 76 \| 13 \| 27 \| 50
1	2	38, 49 \| 65, 97 \| 13, 76 \| 27, 50
2	4	38, 49, 65, 97 \| 13, 27, 50, 76
3	8	13, 27, 38, 49, 50, 65, 76, 97

复杂度：每轮全表扫一遍 $O(n)$ ，n 个元素二路归并需 $\lceil \log_2 n \rceil$ 轮（段长翻倍），总时间 $O(n\log_2 n)$ （与初始状态无关）。空间 $O(n)$ （辅助数组，这是归并的主要代价；递归栈另加 $O(\log_2 n)$ ）。稳定。n 个元素二路归并共需 $\lceil \log_2 n\rceil$ 趟、关键字比较次数介于 $\frac{n}{2}\log_2 n$ 与 $n\log_2 n - n + 1$ （选择题口径：比较次数不超过 $n\lceil\log_2 n\rceil - n + 1$ ）。

五、基数排序

思想：多关键字排序的最低位优先（LSD）法——不比较关键字，而是按位分配 + 收集。设关键字为 d 位、每位基数 r（十进制 r = 10）：

第 1 趟按最低位把 n 个元素分配到 r 个队列（链式，保持先进先出从而保序）；
按 0 → r−1 顺序把各队列收集回序列；
对次低位重复，共 d 趟，收集完成即全局有序。

复杂度：每趟分配 O(n)、收集 O(r)，共 d 趟，时间 $O(d(n + r))$ ；与 n 的大小无关的比较不存在——它是非比较排序，d、r 固定时接近线性。空间 $O(r)$ （r 个队列）加 $O(n)$ 链指针。稳定（队列 FIFO 保证同关键字保序——排序基数表示例必须稳定，否则高位重新分配时低位结果被破坏）。适用：关键字位数 d 小、每位取值范围 r 小且固定（整数、定长字符串如扑克牌），且可分解；不适合任意浮点比较。

六、复杂度与稳定性总对比

算法	最好	平均	最坏	空间	稳定	备注
直接插入	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	基本有序/n 小最优选
折半插入	$O(n^2)$ （比较 $O(n\log_2 n)$ ，移动不减）	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	只减比较次数
希尔	依增量序列，约 $O(n^{1.3})$	同左	同左	$O(1)$	不稳定	首个破 $O(n^2)$
冒泡	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	最好情形靠"无交换提前终止"
快速排序	$O(n\log_2 n)$	$O(n\log_2 n)$ （常数最小）	$O(n^2)$ （初始有序+首枢轴）	$O(\log_2 n)$ ，最坏 $O(n)$	不稳定	每趟枢轴落最终位
简单选择	$O(n^2)$ （比较恒 $\frac{n(n-1)}{2}$ ）	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定	比较次数与初态无关
堆排序	$O(n\log_2 n)$	$O(n\log_2 n)$	$O(n\log_2 n)$	$O(1)$	不稳定	建堆 $O(n)$ ；Top-k 利器
二路归并	$O(n\log_2 n)$	$O(n\log_2 n)$	$O(n\log_2 n)$	$O(n)$	稳定	n log n 中唯一稳定
基数	$O(d(n+r))$	$O(d(n+r))$	$O(d(n+r))$	$O(r)$	稳定	非比较排序

稳定性记忆口诀："考研不稳的四种：快选希堆（快些选一堆）"，其余（插冒归基）稳定。

七、排序过程类选择题的推演方法（套路总结）

题型：给初始序列与某趟之后的中间结果，问是哪种排序。判别按三个维度：

维度一：每趟是否有元素到达最终位置

特征	算法
每趟至少一个元素落最终位	冒泡（最大沉底）、快排（枢轴落位）、简单选择（最小升头）、堆排序（堆顶出堆到尾部）
每趟不保证元素最终位	直接/折半插入（只保证前缀有序）、希尔（只保证增量组内有序）、归并（只保证有序段变长）、基数（只保证低 i 位全序）

维度二：看"就位元素"出现在哪一端、什么形态

尾部就位、从大数开始：冒泡、堆排序（升序）。区分：冒泡后尾部一段是全局最大的若干个且前面的部分近似整体偏移；堆排序每趟尾部就位一个，但前部非有序（仍是堆的松散形态，常见"前大后无序"的堆特征：r₁ 为剩余最大）。
头部就位、从小数开始：简单选择（升序）。
中部就位、其左全小其右全大：快排——这是快排的专属指纹：找一个元素 x，检验"左边全部 ≤ x ≤ 右边全部"。注意：冒泡第一趟后也恰好最大值在尾，若枢轴恰好也是最大值（取首元素为枢轴且首元素最大）会与冒泡同形，需再查第二趟或检查"左侧是否有多个小者同时变化"。

维度三：看有序区的形态与增长方式

前缀有序、长度每趟 +1：直接插入。指纹：前缀内部保持原有相对顺序、后缀完全未动。
前缀有序、但前缀元素可能是跳跃换来的（前缀不是原序列的连续前段）：简单选择（交换可能打乱中间元素次序）。
增量子序列各自有序：希尔。
有序段长度每趟翻倍（1→2→4→…）：二路归并。
低 k 位整体有序（如个位十位递增）：基数。

实战演示（模拟题）：初始 {45, 78, 12, 90, 34, 65}，第一趟后为 {34, 12, 45, 90, 78, 65}。检验元素 45：位置 3，左侧 {34, 12} 全部 < 45，右侧 {90, 78, 65} 全部 > 45——快排指纹，枢轴 45（首元素）。再验证排除项：冒泡第一趟应为 {45, 12, 78, 34, 65, 90}（90 沉底）；简单选择第一趟为 {12, 45, 78, 90, 34, 65}（12 升头）；直接插入第一趟不动（45 < 78，前缀已有序），仍 {45, 78, 12, 90, 34, 65}。

配套速查（"每趟结果"互异指纹一览，待动画化）：

算法	第一趟后的可检验特征（对任意序列）
直接插入	r₁ ≤ r₂，其余位置未动
冒泡	最大值在最末；且每对相邻逆序都消过一遍
快排	存在元素 x 满足"左全 ≤ x ≤ 右全"
简单选择	最小值在 r₁
希尔(d)	相距 d 的子序列各自有序
堆排序	r₁ 为全序列最大；整体不是有序（对比简单选择降序版）
二路归并	r₁ ≤ r₂、r₃ ≤ r₄、…（相邻对有序）

八、外部排序

场景：数据量远超内存，文件分块读入内存（工作区）排序后写回外存，再多轮归并——磁盘读写次数是主导代价，优化目标是减少读写与归并趟数。

多路平衡归并

流程：① 内存工作区能装 w 个记录，逐块读入、内部排序成初始归并段（等长 w，最后一段可短）写回外存，设共 r 段；② 每次 k 个段为一组归并（k 路归并），一趟后段数变为 $\lceil r/k \rceil$ ；③ 直到合成 1 段。归并趟数：

$S = \lceil \log_k r \rceil$

每趟每个记录读写一遍，减少 S 的两条路：增大初始段长（减少 r，见置换选择）、增大归并路数 k。但 k 路归并每输出一个记录要 k−1 次关键字比较（选 k 段首中最小），k 大时比较开销成为新瓶颈——引出败者树。

败者树（Tree of Losers）

k 路归并的选择优化：完全二叉树结构，叶子为 k 个归并段当前的队首记录，内部结点记录左右比较中的"败者"（较大者）所在段号，胜者（较小者）继续向上，根的上方（冠军结点）即当前最小。每输出一个记录、其段补入新队首后，只需从该叶子到根的路径重赛：比较次数 $\lceil \log_2 k \rceil$ （内部结点共 k − 1 个，但重赛只走一条路径）——把每记录 k−1 次比较降到 $\lceil\log_2 k\rceil$ 次，且与 k 的增长解耦，使 100+ 路归并在工程上可行。胜者树 vs 败者树：胜者树内部结点记胜者，更新时需知道兄弟（从双亲读到的不是自己的对手）；败者树直接读双亲就能开打，更新更快——这是"为什么用败者树"的标准答案。

置换选择排序（生成更长的初始归并段）

工作区 w 个记录，维护一个 w 结点小顶堆：

输出堆顶（当前最小，属于当前归并段）到输出缓冲区；
从输入读下一个记录补位：若它 ≥ 刚输出的堆顶，可留在当前段（将来还能排在它后面）；若更小，它不能进当前段（会破坏段内有序），标记冻结，暂存；
堆调整时跳过冻结记录；当所有记录冻结，当前段终止、开启新段，冻结者解冻成新段的堆。

理论结论：初始归并段平均长度为 2w（内存翻倍效应，无严格上界保证、随数据分布波动）。代价 0 趟额外读写——只是边扫边生成。

最佳归并树（哈夫曼思想的迁移）

r 个不等长初始归并段做 k 路归并，归并树带权路径长度 WPL = Σ(段长 × 该段到根的路径长) 正比于总读写量（每归并一层，段内所有记录读写一遍）——总读写次数 = 2 × WPL（读 + 写各一遍，选择题按此口径）。让 WPL 最小的归并树即最佳归并树：每次合并当前最小的 k 段，哈夫曼树的 k 叉推广。

补虚段：严格 k 叉哈夫曼树要求 $(r - 1) \bmod (k - 1) = 0$ ；若不满足，需补

$u = (k - 1) - (r - 1) \bmod (k - 1)$

个长度为 0 的虚段参与归并（虚段无读写开销，只占位凑满 k 叉）。

例（模拟题）：9 个初始归并段长 {9, 30, 12, 18, 3, 17, 2, 6, 24}，3 路归并： $u = 2 - (8 \bmod 2) = 0$ ，不需补段。反复取最小 3 段合并：{2,3,6}→11；{9,11,12}→32；{17,18,24}→59；{30,32,59}→121。WPL = 2×(2+3+6) + 2×(9+11+12) + 2×(17+18+24) + 121 … 逐段数路径长：段 2,3,6 深 3；9,12 深 2（11 是新段）；11 深 2；17,18,24 深 2；30 深 1；32 深 1；59 深 1。WPL = (2+3+6)×3 + (9+12+11)×2 + (17+18+24)×2 + (30+32+59)×1 = 33 + 64 + 118 + 121 = 336，总读写 672 次（单位：记录的整段读写遍数按题目口径）。

例题

例 1（模拟题）：序列 {49, 38, 65, 97, 76, 13, 27, 50} 以 49 为枢轴（首元素）做一趟快排划分，结果是（）

A. {27, 38, 13, 49, 76, 97, 50, 65} B. {13, 27, 38, 49, 65, 50, 76, 97} C. {27, 38, 13, 49, 65, 97, 50, 76} D. {27, 38, 50, 49, 76, 13, 65, 97}

解答：选 A。完整推演见第二节分步表。判别指纹复核：49 左侧 {27, 38, 13} 全小、右侧 {76, 97, 50, 65} 全大 ✓。错因提醒：B 是两趟后的形态（左侧子区间也排完），D 是"从左找大填右"的动作顺序错乱的典型错值。

例 2（模拟题）：对 {50, 36, 66, 90, 14, 22, 5, 18} 自底向上建大顶堆的结果是（）

A. {90, 50, 66, 36, 14, 22, 5, 18} B. {90, 66, 50, 36, 22, 18, 14, 5} C. {90, 50, 66, 18, 14, 22, 5, 36} D. {66, 50, 90, 36, 14, 22, 5, 18}

解答：选 A。从 ⌊8/2⌋ = 4 倒序调整，见第三节分步表。错因提醒：C 是漏掉了 36 下沉后继续与孩子 18 比较（实际 36 > 18 无需再动，C 错在把 36 与 18 又交换）；B 是"每次把最大值逐一冒泡"的错误思路。

例 3（模拟题）：下列排序中，比较次数与序列初始状态无关的是（）

A. 快速排序 B. 直接插入 C. 简单选择 D. 冒泡排序

解答：选 C。简单选择每趟必须扫完整个无序区确定最小者，比较恒 $\frac{n(n-1)}{2}$ ；A 依赖枢轴落位、B 依赖"是否已小于前缀尾"可提前停、D 依赖"本趟有无交换"（有序时可提前终止）。错因提醒：折半插入的比较次数也与初态无关（只与 n 有关）——若选项出现折半插入，需与 C 同判"无关"。

常见坑

快排最坏情形是"初始有序/逆序 + 取首（尾）元素为枢轴"，不是"数据有大量重复"；空间最坏 $O(n)$ 是递归深度，别写成 $O(1)$ 。
快排每趟至少一个元素落位，但一趟后子区间内部无序；"一趟后有多个元素到最终位置"是可能的（枢轴恰好选得准），但"不能保证"是标准答案口径。
冒泡的最好情形 $O(n)$ 依赖"无交换提前终止"的实现；若实现无该判断，冒泡最好也是 $O(n^2)$ 。
折半插入总时间仍 $O(n^2)$ ——只省比较、省不了移动，"折半插入是 $O(n\log_2 n)$ "是高频错项。
建堆是 $O(n)$ 、堆排序整体是 $O(n\log_2 n)$ ，两者别混；建堆从 $\lfloor n/2 \rfloor$ 倒序开始，从 1 正序开始是错的。
升序配大顶堆、降序配小顶堆；堆只保证"父 ≥ 子"，同层兄弟无大小关系，"堆顶以下从左到右递减"必错。
归并排序是 $O(n\log_2 n)$ 中唯一稳定的（原地快排不稳定、堆排序不稳定）；空间 $O(n)$ 是辅助数组，是它不如快排常被选用的主因。
基数排序时间 $O(d(n+r))$ 与"关键字比较次数"口径无关（它不比较）；适合位数少、基数小的关键字，不是"任何时候都最快"。
外部排序：趟数 $S = \lceil\log_k r\rceil$ ；败者树比较次数 $\lceil\log_2 k\rceil$ ；置换选择平均段长 2w；最佳归并树补虚段数 $u = (k-1) - (r-1)\bmod(k-1)$ （当 $(r-1)\bmod(k-1) \ne 0$ ），虚段长 0 不计读写。
稳定性口诀"快选希堆"不稳定；判断稳定性一律用最小反例（如 {3, 3, 1}）验证，不要背结论背串。

自测

n = 8 的序列做二路归并，共几趟？若改 4 路归并共几趟？
序列 {12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}（16* 表示与 16 相等的另一个元素）做简单选择排序，排序后 16 与 16* 的相对次序如何？做冒泡排序呢？
含 1024 个记录的文件，初始归并段长 128（即 r = 8），做 4 路归并需几趟？若用败者树，归并阶段每输出一个记录约多少次关键字比较？
判断：对任意输入，堆排序的比较次数总少于归并排序。（对/错，说明理由）
给序列 {5, 4, 3, 2, 1}，以 5 为枢轴（首元素）做一趟划分，结果是什么？由此说明快排在这种输入下的行为。

答案与简析

$\lceil \log_2 8 \rceil = 3$ 趟； $\lceil \log_4 8 \rceil = \lceil 1.5 \rceil = 2$ 趟。
排序结果为 {2, 6, 10, 12, 16, 16*, 18, 20, 28, 30}。逐趟推演会发现本例中 16 与 16* 的次序恰好保持（每次交换的最小元素都未跨过 16），但这只是该输入的巧合——算法层面简单选择不稳定：存在使其颠倒的输入（最小反例 {3, 3, 1}，第一趟 1 与第一个 3 交换后两个 3 次序颠倒）。冒泡稳定，相等不交换，任何输入下 16 必仍在 16* 之前。判稳定性的口径是"是否存在输入使其颠倒"，不是"某一次运行未颠倒"。
$S = \lceil\log_4 8\rceil = 2$ 趟；败者树阶段每记录 $\lceil\log_2 4\rceil = 2$ 次比较。
错。堆排序最坏 $O(n\log_2 n)$ 与归并同阶，但常数上堆排序建堆后每轮调整的比较与具体输入相关；不存在"总少于"的一般结论。两者同为 $O(n\log_2 n)$ ，比较次数互有高低。
一趟划分：{4, 3, 2, 1, 5}——5 的右侧为空（high 端找不到 <5 的元素，一路滑到与 low 相遇），划分极不对称。递归右侧为空、左侧 n−1 个，每趟只减 1，这正是快排在有序输入（首元素枢轴）下退化为 $O(n^2)$ 的机理。

下一步：完成03-查找与排序-章节测的第 13-30 题（限时手推：快排一趟、建堆、各算法每趟指纹判断）。错题记入测验/00-错题本。

#排序

#考点定位

#零、排序的基本概念

#一、插入排序

#直接插入排序

#折半插入排序

#希尔排序（缩小增量排序）

#二、交换排序

#冒泡排序

#快速排序（重点中的重点）

#三、选择排序

#简单选择排序

#堆排序

#四、归并排序（二路归并）

#五、基数排序

#六、复杂度与稳定性总对比

#七、排序过程类选择题的推演方法（套路总结）

#维度一：每趟是否有元素到达最终位置

#维度二：看"就位元素"出现在哪一端、什么形态

#维度三：看有序区的形态与增长方式

#八、外部排序

#多路平衡归并

#败者树（Tree of Losers）

#置换选择排序（生成更长的初始归并段）

#最佳归并树（哈夫曼思想的迁移）

#例题

#常见坑

#自测

排序