第 8 章排序 - 考研笔记

本章整理排序的基本概念、五类内部排序、排序算法比较与外部排序。排序是 408 中“结论密集 + 过程分析”并重的一章：内部排序要能写出每一趟排序后的序列，外部排序要围绕 I/O 次数计算。

复习主线：每种算法先抓“怎么走一趟”和“一趟后哪些元素到位”，再记时间、空间、稳定性三个结论，最后用总表和“比较排序下界”把整章串起来。

排序的基本概念

排序、关键字与稳定性

排序：将一组数据元素按关键字的大小重新排列成递增或递减序列的过程
关键字：数据元素中用于比较排序的属性，可以是单个数据项，也可以是若干数据项的组合
稳定性：若待排序表中两个关键字相同的元素 $R_i$ 、 $R_j$ （排序前 $R_i$ 在 $R_j$ 之前），排序后 $R_i$ 仍在 $R_j$ 之前，则称该排序算法稳定；否则称不稳定

易错点：稳定性是算法本身的性质，与初始序列无关。不能因为某组数据排序后相同关键字次序恰好没变，就判定该算法稳定。

内部排序与外部排序

内部排序：排序期间元素全部存放在内存中
外部排序：元素过多、无法一次全部放入内存，排序过程中需要不断在内存与外存之间移动数据
- 评价外部排序的核心指标是外存 I/O 次数，而不是关键字比较次数
原地排序：辅助空间为 $O(1)$ 。递归调用栈等额外空间也要计入辅助空间

408 中默认待排序表采用顺序存储（数组），可以随机访问；若改为链表，元素移动的代价和部分结论会发生变化，题目会另行说明。

评价指标与算法分类

指标	含义
时间复杂度	比较次数、移动次数等操作的数量级
空间复杂度	排序过程中额外使用的辅助空间
稳定性	相同关键字元素的相对位置是否改变

按思想分类（本章主线）：

插入排序：直接插入、折半插入、希尔排序
交换排序：冒泡排序、快速排序
选择排序：简单选择排序、堆排序
归并排序：二路归并排序
基数排序：按位分配与收集，不属于比较排序

复习方法：每学一种算法，都回答四个问题——怎么走一趟、一趟后哪些元素到位、时间与空间复杂度、是否稳定。

插入排序

插入排序的核心思想：每次把一个待排序元素插入到前面已经有序的子序列中。

直接插入排序：思想与手算过程

基本思想：

初始时，把第一个元素看作长度为 1 的有序子序列
从第 2 个元素起，取出当前元素 $A[i]$ ，在有序区 $A[1..i-1]$ 中从后向前查找插入位置
比 $A[i]$ 大的元素依次后移一位
把 $A[i]$ 放入空出的位置

稳定性关键：从后向前比较时，只有严格大于（>）才后移；遇到相等元素就停下，把待插入元素放在它后面，因此直接插入排序稳定。

以 49 38 65 97 76 13 27 为例，每趟插入一个元素：

趟	待插入	插入后序列
初始	—	49 38 65 97 76 13 27
1	38	38 49 65 97 76 13 27
2	65	38 49 65 97 76 13 27
3	97	38 49 65 97 76 13 27
4	76	38 49 65 76 97 13 27
5	13	13 38 49 65 76 97 27
6	27	13 27 38 49 65 76 97

共

n-1

趟；第

i

趟结束后，前

i+1

个元素有序。

直接插入排序的复杂度与适用场景

最好情况：原序列已经有序，比较 $n-1$ 次、移动 0 次，时间 $O(n)$
最坏情况：原序列逆序，比较和移动次数均约为 $n^2/2$ ，时间 $O(n^2)$
平均情况： $O(n^2)$
空间复杂度： $O(1)$
稳定性：稳定

适用：

n

较小，或序列基本有序时，直接插入排序往往是最快的内部排序之一。

折半插入排序：只减少比较，不减少移动

基本思想：先用折半查找在有序区

A[1..i-1]

中确定插入位置，再统一后移元素、插入。与直接插入排序的区别：

比较项目	直接插入	折半插入
查找插入位置	顺序查找	折半查找
比较次数	较多，与初始序列有关	约 $O(n\log n)$ ，与初始序列无关
移动次数	与初始序列有关	与直接插入相同
时间复杂度	$O(n^2)$	$O(n^2)$
空间复杂度	$O(1)$	$O(1)$
稳定性	稳定	稳定

高频陷阱：折半插入只优化了“找位置”，没有优化“挪元素”。元素移动次数仍可能达到

O(n^2)

，因此总时间复杂度仍是

O(n^2)

，不是

O(n\log n)

。

稳定性的细节：为保证稳定，折半查找应定位到“最后一个不大于待插入元素的元素之后”，使相等元素排在待插入元素之前。

希尔排序：缩小增量，分组插入

基本思想：取一个增量

d

，把相隔

d

的元素分成一组，各组分别做直接插入排序；然后缩小

d

，重复；当

d=1

时对整个序列做一次直接插入排序。增量序列的要求：

最后一个增量必须为 1，否则不能保证最终有序
增量之间通常取互质，避免同一元素在同一组内反复出现，减少重复劳动

以 49 38 65 97 76 13 27 49 为例，取增量

4 \to 2 \to 1

：

趟	增量	分组	本趟结果
1	4	(49,76) (38,13) (65,27) (97,49)	49 13 27 49 76 38 65 97
2	2	(49,27,76,65) (13,49,38,97)	27 13 49 38 65 49 76 97
3	1	整个序列做直接插入排序	13 27 38 49 49 65 76 97

为什么最后一趟必须是 $d=1$ ：只有增量为 1 时，整个序列才作为一组参与插入排序；前面的分组排序只是让序列“更接近有序”，并不能保证全局有序。

希尔排序的复杂度与稳定性

指标	结论
时间复杂度	与增量序列有关；常见最坏为 $O(n^2)$ ，好的增量序列可优于 $O(n^2)$
空间复杂度	$O(1)$
稳定性	不稳定

为什么不稳定：相同关键字的元素可能被分到不同的子序列，跨组移动后相对次序会被打乱。

考点：希尔排序是直接插入排序的改进，但不再是稳定排序；不能因为直接插入稳定就认为希尔也稳定。

交换排序

交换排序的核心思想：通过交换两个元素的位置，使关键字逐渐满足排序要求。

冒泡排序：每趟「沉」一个最值

基本思想：从前往后依次比较相邻元素，若逆序则交换；一趟结束后，最大元素“冒”到末尾，有序区从后向前扩大。关键点：

每趟至少确定一个元素的最终位置，最多 $n-1$ 趟
若某一趟没有发生交换，说明序列已经有序，可以提前结束
相等元素不交换，因此稳定

以 49 38 65 97 76 13 27 49 为例（从前往后、大数下沉）：

趟	比较范围	本趟结果
初始	—	49 38 65 97 76 13 27 49
1	全部	38 49 65 76 13 27 49 97
2	前 7 个	38 49 65 13 27 49 76 97
3	前 6 个	38 49 13 27 49 65 76 97
4	前 5 个	38 13 27 49 49 65 76 97
5	前 4 个	13 27 38 49 49 65 76 97
6	前 3 个	13 27 38 49 49 65 76 97（无交换，提前结束）

第 6 趟没有发生交换，说明序列已经有序，可以提前结束；最坏情况下才需要

n-1

趟。

冒泡排序的复杂度

最好情况：正序且设置提前结束标志，比较 $n-1$ 次，时间 $O(n)$
最坏情况：逆序，比较 $n(n-1)/2$ 次，移动 $3n(n-1)/2$ 次，时间 $O(n^2)$
平均情况： $O(n^2)$
空间复杂度： $O(1)$
稳定性：稳定

与简单选择排序对比：冒泡的交换次数可能很多；简单选择的交换次数最多

n-1

次，但比较次数固定。两者最坏时间同为

O(n^2)

。

快速排序：分治与一趟划分

基本思想（分治）：

选择一个枢轴 pivot（常取第一个元素）
一趟划分：把序列分成左右两部分，左边元素都不大于枢轴，右边元素都不小于枢轴
枢轴落到最终位置
对左右子序列递归执行上述过程

一趟划分的双指针做法：

用 low、high 分别指向待划分区间的两端，pivot = A[low]
先从 high 向左找第一个小于 pivot 的元素，填入 A[low]，low 右移
再从 low 向右找第一个大于 pivot 的元素，填入 A[high]，high 左移
重复直到 low == high，把 pivot 放入该位置

以 49 38 65 97 76 13 27 49 为例，取首元素 49 为枢轴：

步骤	操作	序列
初始	枢轴 49，low=1，high=8	49 38 65 97 76 13 27 49
1	high 找到 27，填 low	27 38 65 97 76 13 * 49
2	low 找到 65，填 high	27 38 * 97 76 13 65 49
3	high 找到 13，填 low	27 38 13 97 76 * 65 49
4	low 找到 97，填 high	27 38 13 * 76 97 65 49
5	low 与 high 相遇于 4，填枢轴	27 38 13 49 76 97 65 49

表中 * 表示当前的待填位置；第 5 步把枢轴放入，得到最终划分结果。

记忆：一趟划分的结果一定是“左小右大 + 枢轴归位”。枢轴左边的元素不一定有序，右边也不一定有序，但分别都不大于、不小于枢轴。

快速排序的复杂度与考点

情况	时间复杂度	原因
最好	$O(n\log n)$	每次划分基本均衡
平均	$O(n\log n)$	划分较为均衡
最坏	$O(n^2)$	每次划分极不均衡

空间复杂度：平均 $O(\log n)$ ，最坏 $O(n)$ ，来自递归调用栈
稳定性：不稳定

高频考点：

每趟划分后，枢轴元素到达最终位置，但左右子序列内部仍可能无序
递归深度取决于划分是否均衡；最坏退化为 $0$ 与 $n-1$ 两部分，递归深度 $O(n)$
待排序序列基本有序（正序或逆序）且取首元素为枢轴时，最坏 $O(n^2)$
快速排序的平均性能在比较排序中最好，但最坏情况不如堆排序、归并排序稳定
枢轴优化：随机选取、三数取中，可降低出现最坏情况的概率

易错：快速排序的空间复杂度不是

O(1)

；递归调用栈也要计入辅助空间。

选择排序

选择排序的核心思想：每一趟从待排序序列中选出最小（或最大）元素，放到最终位置。

简单选择排序：每趟选最小，交换到前面

基本思想：第

i

趟从

A[i..n]

中选出最小元素，与

A[i]

交换；

n-1

趟后全部有序。

比较次数：固定为 $n(n-1)/2$ ，与初始序列无关
移动次数：最多 $n-1$ 次交换，即 $3(n-1)$ 次移动
时间复杂度：最好、平均、最坏均为 $O(n^2)$
空间复杂度： $O(1)$
稳定性：不稳定

不稳定的例子：2 2 1。第一趟把第一个 2 与 1 交换，得到 1 2 2，两个 2 的相对次序被改变。

堆的定义与顺序存储

大根堆：每个结点的值都不小于其左右孩子的值，堆顶为最大值
小根堆：每个结点的值都不大于其左右孩子的值，堆顶为最小值
堆是一棵完全二叉树，通常采用顺序存储

若采用从 1 开始的数组下标，对结点

i

：

左孩子 = 2i,\qquad 右孩子 = 2i+1,\qquad 双亲 = \left\lfloor \frac{i}{2} \right\rfloor

若采用从 0 开始的下标，则左孩子为

2i+1

、右孩子为

2i+2

、双亲为

\lfloor (i-1)/2 \rfloor

。做题时先看题目约定。

升序排序用大根堆：每次把堆顶（最大值）换到数组末尾，堆的有效长度减 1，最终得到升序序列。降序排序则用小根堆。

建堆：从最后一个非叶结点向前调整

建堆过程：从最后一个非叶结点

\lfloor n/2 \rfloor

开始，依次向前对每个结点执行向下调整。

为什么建堆是 $O(n)$ ：越靠近叶子的结点越多，但需要向下调整的高度越低；总代价约为

\sum 2^h \cdot (H-h)

量级，最终为

O(n)

，不是

O(n\log n)

。

以 53 17 78 9 45 65 87 建大根堆：

步骤	调整结点	序列
初始	—	53 17 78 9 45 65 87
1	$i=3$ （78）	53 17 87 9 45 65 78
2	$i=2$ （17）	53 45 87 9 17 65 78
3	$i=1$ （53）	87 45 78 9 17 65 53

第 3 步中，53 先与 87 交换，再继续向下与 78 交换，才得到最终结果。建堆完成后：

堆排序：反复取堆顶

排序过程：

建立初始大根堆
堆顶（最大值）与堆的最后一个元素交换
堆的有效长度减 1，对堆顶执行向下调整
重复第 2、3 步，直到堆中只剩一个元素

接上例，前两趟：

趟	交换	调整后（左侧为堆，右侧为已就位部分）
1	87 与 53	78 45 65 9 17 53 ｜ 87
2	78 与 53	65 45 53 9 17 ｜ 78 87

堆的插入与删除：

插入：新元素放到堆尾，再向上调整， $O(\log n)$
删除堆顶：堆尾元素放到堆顶，再向下调整， $O(\log n)$
在堆中查找某个元素： $O(n)$

向下调整的边界：交换堆顶与堆尾后，堆的有效长度要减 1；调整时不能越过这个边界。

堆排序的复杂度与考点

操作	时间复杂度
建立初始堆	$O(n)$
一次向下调整	$O(\log n)$
删除堆顶、插入	$O(\log n)$
堆排序整体	$O(n\log n)$

最好、平均、最坏：均为 $O(n\log n)$
空间复杂度： $O(1)$
稳定性：不稳定

易错：建堆是

O(n)

，不是

O(n\log n)

；堆排序是原地排序，不需要

O(n)

辅助数组。

归并排序

二路归并的思想与合并过程

基本思想（分治）：

把长度为 $n$ 的序列不断二分，直到每个子序列长度为 1
把相邻的两个有序子序列合并成一个有序序列
反复合并，直到只剩一个序列

合并两个有序表：

两个指针分别指向两个子序列的起始位置
比较指针所指元素，把较小者放入辅助数组，并移动对应指针
某个子序列取完后，把另一个子序列的剩余元素直接复制过去

稳定性关键：两个元素关键字相等时，优先取左边子序列的元素，相同关键字的相对次序保持不变，归并排序稳定。

归并趟数与手动模拟

每趟归并的时间为

O(n)

，共需

\lceil \log_2 n \rceil

趟，因此总时间为

O(n\log n)

。以 49 38 65 97 76 13 27 为例：

趟	子序列划分	本趟结果
初始	每个元素单独成段	49 ｜ 38 ｜ 65 ｜ 97 ｜ 76 ｜ 13 ｜ 27
1	两两归并	38 49 ｜ 65 97 ｜ 13 76 ｜ 27
2	相邻两段归并	38 49 65 97 ｜ 13 27 76
3	最后两段归并	13 27 38 49 65 76 97

归并排序的复杂度与特点

指标	结论
最好、平均、最坏时间	均为 $O(n\log n)$
空间复杂度	$O(n)$ （辅助数组）
稳定性	稳定

时间复杂度始终为 $O(n\log n)$ ，不受初始序列影响
需要与原序列等长的辅助数组，空间开销较大
适合要求稳定且能接受额外空间的场景，也是外部排序的基础

易错：归并排序不是原地排序；它的最坏情况不是

O(n^2)

。

基数排序

低位优先（LSD）的分配与收集

基本思想：不比较关键字大小，而是按关键字的每一位分配、收集，从最低位到最高位依次进行。关键概念：

位数 $d$ ：关键字有多少位
基数 $r$ ：每一位可能的取值个数（十进制数 $r=10$ ）
分配：按当前位的值，把元素放入对应的队列
收集：按队列编号从小到大把元素串起来

前提：每一趟分配、收集必须稳定。否则前面几趟排好的低位次序会被破坏，最终结果错误。

三趟基数排序的手动模拟

以 278 109 063 930 589 184 505 269 008 083 为例，基数为 10：

趟	按哪一位	收集后序列
初始	—	278 109 063 930 589 184 505 269 008 083
1	个位	930 063 083 184 505 278 008 109 589 269
2	十位	505 008 109 930 063 269 278 083 184 589
3	百位	008 063 083 109 184 269 278 505 589 930

不足

d

位的关键字高位补 0（如 008），保证每一趟都按相同的位数处理。

基数排序的复杂度与适用条件

T(n) = O\big(d(n+r)\big)

指标	结论
时间复杂度	$O(d(n+r))$
空间复杂度	$O(n+r)$ （ $r$ 个队列 + $n$ 个结点）
稳定性	稳定

属于非比较排序，不受 $\Omega(n\log n)$ 下界限制
时间复杂度与初始序列无关，只取决于 $d$ 、 $n$ 、 $r$
适合关键字位数少、位数统一、基数小的数据
不适合位数很多、位数差异大或浮点数数据

有的教材只统计

r

个队列的辅助空间，把空间复杂度记作

O(r)

。

计数排序（拓展）

统计、前缀和与回填

基本思想：

统计每个关键字值出现的次数
对次数做前缀和，得到每个值在有序序列中的最后位置
从后向前遍历原序列，把元素放到对应位置，并让该位置前移

时间复杂度： $O(n+k)$ ， $k$ 为关键字值域大小
空间复杂度： $O(n+k)$ （结果数组 + 计数数组）
稳定性：按上述“从后向前回填”实现时稳定
适用条件：关键字为整数且值域较小

计数排序不在 408 大纲要求内，作为与基数排序对照的拓展了解即可。

内部排序算法的比较

复杂度与稳定性总表

时间复杂度

排序算法	最好	平均	最坏
直接插入	$O(n)$	$O(n^2)$	$O(n^2)$
折半插入	$O(n^2)$	$O(n^2)$	$O(n^2)$
希尔排序	与增量有关	与增量有关	与增量有关
冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$
快速排序	$O(n\log n)$	$O(n\log n)$	$O(n^2)$
简单选择	$O(n^2)$	$O(n^2)$	$O(n^2)$
堆排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$
归并排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$
基数排序	$O(d(n+r))$	$O(d(n+r))$	$O(d(n+r))$

空间复杂度与稳定性

排序算法	空间复杂度	稳定性
直接插入	$O(1)$	稳定
折半插入	$O(1)$	稳定
希尔排序	$O(1)$	不稳定
冒泡排序	$O(1)$	稳定
快速排序	平均 $O(\log n)$	不稳定
简单选择	$O(1)$	不稳定
堆排序	$O(1)$	不稳定
归并排序	$O(n)$	稳定
基数排序	$O(n+r)$	稳定

折半插入的记法：教材通常把它的时间复杂度统一记为

O(n^2)

，因为瓶颈在移动次数。若题目只问比较次数，则为

O(n\log n)

，且与初始序列无关。

稳定性与复杂度的记忆

稳定：直接插入、折半插入、冒泡、归并、基数不稳定：希尔、快速、简单选择、堆

口诀：插入冒泡归并基数稳定；希尔快排选择堆不稳定。

按时间复杂度分层：

$O(n^2)$ ：直接插入、折半插入、冒泡、简单选择、希尔（常见最坏）
$O(n\log n)$ ：快速（平均）、堆、归并
线性级：基数 $O(d(n+r))$ 、计数 $O(n+k)$

比较排序的时间下界

基于关键字比较的排序算法，最坏情况至少需要

\Omega(n\log n)

次比较。

快速排序、堆排序、归并排序都属于比较排序
基数排序、计数排序通过“分配、统计”确定位置，不属于比较排序，因此不受该下界限制

直观理解：

n

个元素有

n!

种排列，每次比较最多把可能性减半，至少需要

\log_2(n!)=\Theta(n\log n)

次比较。

特殊结论速查

问题	结论
一趟排序后能确定元素最终位置	冒泡、快速、简单选择、堆排序
一趟排序后不能确定任何元素最终位置	直接插入、折半插入、希尔、归并、基数
比较次数与初始序列无关	折半插入（比较次数）、简单选择
排序趟数受初始序列影响	冒泡（可提前结束）、快速（划分越不均衡，递归越深）
排序趟数固定	直接插入、简单选择、堆排序、归并、基数
最好情况可达 $O(n)$	直接插入、冒泡
最坏仍为 $O(n\log n)$	堆排序、归并排序
空间 $O(n)$	归并排序
空间 $O(\log n)$	快速排序（平均）
不稳定但最坏 $O(n\log n)$	堆排序
稳定且 $O(n\log n)$	归并排序

“一趟能确定最终位置”不等于“一趟后序列有序”。快排一趟只确定枢轴，归并一趟可能让整体更有序，但不能确定任何元素的最终位置。

内部排序算法的选择

按题目要求选算法

题目要求	推荐算法
数据基本有序	直接插入排序
要求稳定且 $O(n\log n)$	归并排序
平均性能最好	快速排序
要求最坏 $O(n\log n)$ 且原地	堆排序
数据量太大、不能全部装入内存	外部排序
关键字位数固定、基数小	基数排序
关键字为小范围整数	计数排序（拓展）
只要求选出前 $k$ 个最大或最小元素	堆排序（建堆后取 $k$ 次）

几组容易混淆的对比

快速排序与归并排序

快排：平均最快、辅助空间小、不稳定、最坏 $O(n^2)$
归并：稳定、最坏也有 $O(n\log n)$ 、需要 $O(n)$ 辅助空间

快速排序与堆排序

快排：平均 $O(n\log n)$ ，最坏 $O(n^2)$
堆排序：最坏仍为 $O(n\log n)$ ，但实际常数较大、不稳定

冒泡排序与简单选择排序

冒泡：稳定、可提前结束、最好 $O(n)$
简单选择：不稳定、比较次数固定为 $n(n-1)/2$ 、交换次数少

直接插入与希尔排序

直接插入：稳定、适合基本有序的数据
希尔：不稳定、通过分组让序列快速接近有序

外部排序

为什么外部排序关注 I/O

待排序文件太大，无法一次全部放入内存，需要借助外存
排序过程分为两个阶段：
1. 生成初始归并段：分批读入内存，排好序后写回外存
2. 多路归并：把多个有序归并段合并，直到得到一个完整的有序文件
总时间约为“内部排序时间 + 外存读写时间 + 内部归并时间”；数据量大时，读写时间占主导
主要性能瓶颈是磁盘 I/O 次数，而不是关键字比较次数

每趟归并都要把全部数据读入、写出各一次，因此减少归并趟数是外部排序优化的核心。

多路平衡归并与归并趟数

每次同时归并

k

个有序段，称为 $k$ 路归并。若有

r

个初始归并段，则归并趟数为：

S = \left\lceil \log_k r \right\rceil

增大 $k$ 可以减少归并趟数，从而减少 I/O
$k$ 越大，需要的内存缓冲区越多，且从 $k$ 个元素中选最小值的比较开销越大
败者树正是为了降低“从 $k$ 路中选最小”的开销

注意：

k

路归并需要

k

个输入缓冲区加 1 个输出缓冲区；

k

受内存容量限制，不能无限增大。

例：

r=16

，

k=2

时

S=4

；

k=4

时

S=2

。

若文件共

N

个记录，内存工作区可容纳

m

个记录，传统方法生成的初始归并段数为

r=\lceil N/m \rceil

；置换-选择排序可使平均段长约为

2m

，从而减少

r

。

败者树：快速选出 k 路中的最小值

作用：在多路归并中快速确定当前

k

个待选元素中的最小者。结构：

叶结点：各归并段当前参与比较的元素
内部结点：记录一次比较中的败者
另设一个变量记录冠军（当前最小元素）

图中 4 路归并的冠军是 b1（8），单独记录在 ls[0] 中；根结点记录的是最后一次比较的败者 b3。调整过程：

输出冠军所在归并段的下一个元素，替换该叶结点
从该叶结点向上，与路径上记录的败者比较
胜者继续向上，败者留在当前结点
根结点上方得到新的冠军

初始化建树： $O(k)$
每次输出后调整： $O(\log k)$

考点：败者树解决的是“如何快速选出最小值”，它不决定归并段的合并顺序；决定合并顺序、使总 I/O 最小的是最佳归并树。

置换-选择排序：生成长度超过内存的归并段

目的：传统方法中，初始归并段长度不超过内存工作区容量

m

，段数多、归并趟数多。置换-选择排序可以生成长度大于 $m$ 的归并段。过程：

把内存工作区装满记录
选出其中最小者输出，记下刚输出的值 last
从外存读入一条新记录补入工作区
若新记录不小于 last，它可以留在当前归并段；否则冻结，留给下一个归并段
当前归并段无法继续输出时，本段结束；解冻冻结记录，开始生成下一段

结论：随机输入下，置换-选择排序生成的初始归并段平均长度约为

2m

。

意义：段数

r

减少，归并趟数

S=\lceil \log_k r \rceil

减少，I/O 次数随之减少。

最佳归并树：让总 I/O 最小

各初始归并段长度不同，不同的归并顺序会产生不同的总读写代价。把归并段长度作为叶结点权值，构造 $k$ 叉哈夫曼树，即为最佳归并树。构造方法：

每次选取权值最小的 $k$ 个结点
合并成一个新结点，权值为这 $k$ 个结点权值之和
把新结点放回，重复直到只剩一个结点

带权路径长度：

WPL = \sum_{i=1}^{n} w_i l_i

其中

w_i

为第

i

个归并段的长度，

l_i

为该叶结点在归并树中的深度。

WPL

越小，总读写次数越少。虚段补齐：

k

叉哈夫曼树要求

(n-1) \bmod (k-1) = 0

若不满足，需要补充权值为 0 的虚段，补

k-1-\big((n-1)\bmod(k-1)\big)

个（余数不为 0 时）。

注意：

n

是补虚段前的归并段数；补 0 权虚段不增加实际归并代价；2 路归并（

k=2

）时

k-1=1

，一定整除，不需要补虚段。

例 1：

k=3

、

n=8

。

(8-1)\bmod 2=1

，需补

3-1-1=1

个虚段，按 9 个叶结点构造三叉哈夫曼树。例 2：

k=3

，归并段长度为 2 3 5 7 11。

(5-1)\bmod 2=0

，无需补虚段。

合并 2、3、5，得到 10
合并 7、10、11，得到 28
$WPL = 10 + 28 = 38$

高频易错点

结论判断易错清单

易错说法	正确结论
折半插入排序是 $O(n\log n)$	仍为 $O(n^2)$ （只减少比较，不减少移动）
希尔排序稳定	不稳定
快速排序稳定	不稳定
简单选择排序稳定	不稳定
冒泡排序最好情况是 $O(n^2)$	设置提前结束标志后为 $O(n)$
建堆是 $O(n\log n)$	建堆为 $O(n)$
堆排序需要 $O(n)$ 辅助空间	通常为 $O(1)$
归并排序是原地排序	通常需要 $O(n)$ 辅助空间
归并排序最坏为 $O(n^2)$	为 $O(n\log n)$
快速排序最坏为 $O(n\log n)$	为 $O(n^2)$
基数排序依赖关键字比较	属于非比较排序
败者树用于生成初始归并段	败者树用于多路归并选最小值；生成初始归并段用置换-选择排序
最佳归并树使用等长归并段	按各段长度构造哈夫曼树
稳定性与初始序列有关	稳定性是算法本身的性质

过程分析易错点

直接插入第 $i$ 趟是把 $A[i+1]$ 插入前 $i$ 个元素，注意不要数错趟数
冒泡每趟确定的是当前无序区的最大值，放在无序区末尾
快排一趟只保证枢轴到位，枢轴两侧内部仍可能无序
堆排序中交换堆顶与堆尾后，堆的有效长度要减 1，调整时不能越过边界
归并排序的手算要按“两两归并”进行，不要跨段随意合并
基数排序通常按低位优先（LSD），且每趟稳定

检查方法：手算排序过程时，每一步都问自己“这一步之后，哪些元素的位置已经不会再变了”。

考前速记

一页纸结论

稳定性：稳定——直接插入、折半插入、冒泡、归并、基数；不稳定——希尔、快速、简单选择、堆。

$O(n^2)$ ：直接插入、折半插入、冒泡、简单选择、希尔（常见最坏）
$O(n\log n)$ ：快速（平均）、堆、归并
线性级：基数 $O(d(n+r))$ 、计数 $O(n+k)$
最好 $O(n)$ ：直接插入、冒泡
最坏仍 $O(n\log n)$ ：堆、归并
辅助空间 $O(1)$ ：直接插入、折半插入、希尔、冒泡、简单选择、堆
辅助空间 $O(\log n)$ ：快速排序（递归栈）
辅助空间 $O(n)$ ：归并排序；基数排序为 $O(n+r)$

关键特殊结论

折半插入：减少比较，不减少移动
冒泡：一趟确定一个最值的最终位置
快速：一趟划分确定枢轴最终位置
堆：建堆 $O(n)$ ，整体 $O(n\log n)$
归并：稳定，但需要辅助空间
基数：每一趟必须稳定
外部排序：核心是减少 I/O 次数
败者树：提高多路归并选最小值的效率
最佳归并树：哈夫曼树思想， $WPL$ 最小

建议重点掌握的题型

排序过程分析：给定初始序列，写出每一趟排序后的结果
快速排序：枢轴划分过程、递归过程、最好与最坏情况
堆排序：建堆、删除堆顶、向下调整
排序算法比较：时间复杂度、空间复杂度、稳定性
归并排序：归并过程、归并趟数、辅助空间
外部排序：多路归并、败者树、置换-选择、最佳归并树

下一步：排序算法的代码实现（快速排序的 Partition、堆的向下调整）和手动模拟可以单独整理成专题，与本章的结论表配合复习。

​排序的基本概念

​插入排序

​交换排序

​选择排序

​归并排序

​基数排序

​计数排序（拓展）

​内部排序算法的比较

​内部排序算法的选择

​外部排序

​高频易错点

​考前速记

排序的基本概念

插入排序

交换排序

选择排序

归并排序

基数排序

计数排序（拓展）

内部排序算法的比较

内部排序算法的选择

外部排序

高频易错点

考前速记