第 8 章排序

408 数据结构第 8 章排序复习讲义，涵盖核心概念、重点考点与典型题型。

一、第 8 章到底在研究什么？

第 8 章的考纲包括：

排序基本概念
插入排序
- 直接插入排序
- 折半插入排序
- 希尔排序
交换排序
- 冒泡排序
- 快速排序
选择排序
- 简单选择排序
- 堆排序
二路归并排序
基数排序
外部排序
各种排序算法的比较和应用

资料将排序分成：

排序
├─ 内部排序
│  ├─ 插入排序
│  │  ├─ 直接插入
│  │  ├─ 折半插入
│  │  └─ 希尔排序
│  ├─ 交换排序
│  │  ├─ 冒泡排序
│  │  └─ 快速排序 ★★★★★
│  ├─ 选择排序
│  │  ├─ 简单选择
│  │  └─ 堆排序 ★★★★★
│  ├─ 归并排序 ★★★★★
│  └─ 基数排序
│
└─ 外部排序
   └─ 多路归并
      ├─ 败者树
      ├─ 置换-选择排序
      └─ 最佳归并树

内部排序意味着待排序数据能够全部装入内存；外部排序则是数据太大，只能一部分一部分调入内存，因此真正影响性能的往往不是 CPU 比较，而是磁盘 I/O。

二、8.1 排序基本概念

1. 什么叫排序？

有记录：

R_{1}, R_{2}, \dots, R_{n}

关键字分别为：

k_{1}, k_{2}, \dots, k_{n}

排序就是重新排列这些记录，使得：

k_{1}^{'} \leq k_{2}^{'} \leq \dots \leq k_{n}^{'}

最常见的是按关键字非递减排序。

三、一个贯穿全章的核心概念：稳定性

这是选择题超级高频点。

假设有两个关键字相同的元素：

4 9_{1}, 4 9_{2}

原来：

4 9_{1}

在

4 9_{2}

之前。

排序以后如果仍然满足：

4 9_{1} 在 4 9_{2} 前面

则算法稳定。

如果变成：

4 9_{2}, 4 9_{1}

就不稳定。

一定要记住

稳定：

直接插入排序
折半插入排序
冒泡排序
归并排序
基数排序

不稳定：

希尔排序
快速排序
简单选择排序
堆排序

资料特别指出，在常见平均时间复杂度达到

O (n lo g_{2} n)

的比较排序中，归并排序是稳定的。

一个记忆方式：

“插冒归基稳，希快选堆不稳。”

但不要只死记。考研有时会问“为什么不稳定”，你必须会构造反例。

例如简单选择排序：

2_{1}, 2_{2}, 1

第一趟把最小的 $1$ 与 $2_{1}$ 交换：

1, 2_{2}, 2_{1}

两个 $2$ 的相对次序改变，所以不稳定。

四、8.2 插入排序

插入排序统一思想只有一句：

前面已经有序，现在把一个新元素插到正确位置。

就像整理扑克牌。

五、直接插入排序

假设：

有序部分          当前元素       未处理部分
A[1...i-1]         A[i]         A[i+1...n]

处理 $A [i]$ 时做三件事：

找到插入位置；
比它大的元素整体后移；
把 $A [i]$ 插进去。

资料使用序列：

4 9_{1}, 38, 65, 97, 76, 13, 27, 4 9_{2}

例如：

第一开始：

4 9_{1}, 38, 65, 97, 76, 13, 27, 4 9_{2}

插入 $38$ ：

38, 4 9_{1}, 65, 97, 76, 13, 27, 4 9_{2}

插入 $65$ ：

38, 4 9_{1}, 65, 97, 76, 13, 27, 4 9_{2}

继续下去，最后得到：

13, 27, 38, 4 9_{1}, 4 9_{2}, 65, 76, 97

注意两个 $49$ 的顺序没有变化，所以稳定。

直接插入排序的关键代码思想

资料中的核心代码可以概括为：

for (i = 2; i <= n; i++) {
    if (A[i] < A[i - 1]) {
        A[0] = A[i];

        for (j = i - 1; A[0] < A[j]; j--)
            A[j + 1] = A[j];

        A[j + 1] = A[0];
    }
}

这里 $A [0]$ 是“哨兵/暂存单元”。

需要真正理解：

待插元素先拿出来
        ↓
比它大的元素不断右移
        ↓
出现 ≤ 待插元素的元素
        ↓
插入它后面

时间复杂度

最好情况：本身有序

例如：

1, 2, 3, 4, 5

每个新元素只和前一个比较一下。

所以：

T (n) = O (n)

最坏情况：完全逆序

例如：

5, 4, 3, 2, 1

每次新元素都要一路移动到最前面。

比较、移动量级都是：

1 + 2 + \dots + (n - 1)

因此：

T (n) = O (n^{2})

平均：

O (n^{2})

空间：

O (1)

稳定。

非常重要的应用判断

如果题目说：

序列已经“基本有序”。

直接插入排序通常非常合适。

这是因为逆序对很少，移动次数很少。

六、折半插入排序

这是一个非常容易出坑的地方。

很多人看到“折半”就认为：

O (n lo g n)

错。

折半插入只是：

用二分查找来寻找插入位置。

原来的直接插入：

寻找位置：顺序查
移动元素：后移

折半插入：

寻找位置：二分查找
移动元素：仍然后移

虽然寻找插入位置的比较次数降低了，但是移动元素的问题完全没解决。

于是：

比较次数 = O (n lo g n)

但：

移动次数 = O (n^{2})

最终仍然：

T (n) = O (n^{2})

空间：

O (1)

稳定。

配套模拟题正好考到了：

“折半插入排序的时间复杂度是 $O (n lo g_{2} n)$ 。”

这是错误的。资料答案明确指出：比较虽然降为对数量级，但移动仍是平方量级。

七、希尔排序

希尔排序可以理解成：

让元素先“大步移动”，快速消灭远距离逆序；最后再用一次普通插入排序收尾。

直接插入排序最大的问题是：

如果一个很小的数在数组最后：

9, 8, 7, 6, 5, 4, 3, 2, 1

那么 $1$ 只能：

一步
一步
一步
一步
...

慢慢往前挪。

希尔排序则让它先跨很多格移动。

1. 增量

假设：

n = 8

可以取：

d_{1} = 4, d_{2} = 2, d_{3} = 1

当：

d = 4

时：

A1 A5
A2 A6
A3 A7
A4 A8

每组分别做插入排序。

然后：

d = 2

最后：

d = 1

当 $d = 1$ 时，本质上就是普通直接插入排序。

但此时整个序列已经非常接近有序，所以最终一趟非常快。

2. 为什么不稳定？

因为两个相等元素可能分进不同的增量组。

一个元素可能经过跨组的大步移动越过另一个相等元素。

所以：

希尔排序不稳定

资料指出，希尔排序空间复杂度：

O (1)

而其时间复杂度依赖增量序列，不能简单像其他排序一样给出统一精确结果；资料给出的常见描述是常见规模下约

O (n^{1.3})

最坏可退化到：

O (n^{2})

并且只适合顺序存储。

考研更重要的不是背 $1.3$ ，而是记住：

希尔排序的时间复杂度与增量序列有关。

八、8.3 交换排序

交换排序：

通过比较元素，并交换它们的位置使序列逐渐有序。

主要两种：

冒泡排序
快速排序

其中快速排序远重要于冒泡排序。

九、冒泡排序

冒泡排序只比较相邻元素。

例如从左往右：

5 2 4 1

比较：

5 > 2

交换：

2 5 4 1

再比较：

5 > 4

变成：

2 4 5 1

再比较：

5 > 1

变成：

2 4 1 5

于是这一趟：

5

已经到了最终位置。

冒泡的核心特征

每一趟至少确定一个元素的最终位置。

这个特点很重要，因为“根据中间序列判断排序算法”经常考。

资料中的实现带有 flag：

if (本趟完全没交换)
    return;

如果一整趟一个交换都没有发生，说明：

A_{1} \leq A_{2} \leq \dots \leq A_{n}

已经有序，可以提前结束。

复杂度

最好：

O (n)

最坏：

O (n^{2})

平均：

O (n^{2})

空间：

O (1)

稳定。

为什么稳定？

因为只交换：

A [i] > A [i + 1]

如果相等，不交换。

资料还强调：

冒泡每趟形成的已排序部分具有全局有序性，即已经冒出来的元素已经是整个序列的最终元素，而插入排序前面的“有序子序列”只是局部有序。

十、快速排序 ★★★★★

这是本章最重要的算法之一。

一定要理解三件事：

Partition 划分在干什么；
为什么平均 $O (n lo g n)$ ；
为什么有序序列反而可能最坏。

十一、快速排序的核心思想

假设选择：

p i v o t = 49

经过一次划分以后：

所有 < 49 的数 | 49 | 所有 >= 49 的数

关键点：

49 已经到最终位置。

但左右两边各自还不一定有序。

于是递归：

QuickSort(左边)
QuickSort(右边)

最终完成排序。

资料对序列

4 9_{1}, 38, 65, 97, 76, 13, 27, 4 9_{2}

执行第一次划分后得到：

{27, 38, 13}, 4 9_{1}, {76, 97, 65, 4 9_{2}}

这里左侧：

27, 38, 13 < 4 9_{1}

右侧：

76, 97, 65, 4 9_{2} \geq 4 9_{1}

所以：

4 9_{1}

已经永久确定了位置。

十二、Partition 为什么要“右边先找”？

资料的经典版本是：

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;

这里有一个很容易困惑的问题：

为什么保存了左端的 pivot 后，要从右边先找？

因为：

A[low]

这个位置已经被暂存到 pivot，相当于出现了一个“空位”。

首先从右边找一个：

< p i v o t

的数来填左边这个空位。

然后右边又出现空位。

再从左边找一个：

> p i v o t

的数去填右边空位。

所以整个过程其实是：

pivot暂存
↓
左边出现坑
↓
从右边找小元素填坑
↓
右边出现坑
↓
从左边找大元素填坑
↓
……
↓
low == high
↓
pivot填最后一个坑

这样理解比单纯背代码容易得多。

十三、快速排序为什么快？

假设每次都能非常均匀地分成两半。

第一层：

n

第二层总元素数仍约：

n

第三层总元素数仍约：

n

递归层数约：

lo g_{2} n

所以：

T (n) = O (n lo g_{2} n)

更严格写：

T (n) = 2 T (\frac{n}{2}) + O (n)

得到：

T (n) = O (n lo g_{2} n)

十四、快速排序最坏情况

假设每次取第一个元素为枢轴。

数组已经递增：

1, 2, 3, 4, 5, 6

第一次：

p i v o t = 1

得到：

空 | 1 | 2 3 4 5 6

第二次：

p i v o t = 2

又是：

空 | 2 | 3 4 5 6

每次只减少一个元素。

比较次数接近：

(n - 1) + (n - 2) + \dots + 1

因此：

T (n) = O (n^{2})

递归深度：

O (n)

资料明确指出，初始序列基本有序或基本逆序时，如果枢轴选择不合理，容易出现这种情况。可以采用“三数取中”或随机枢轴改善划分。

十五、快速排序空间复杂度

最好/平均：

O (lo g_{2} n)

原因是递归栈深度约为：

lo g_{2} n

最坏：

O (n)

因此不能说快速排序是：

O (1)

空间。

十六、快速排序几个必考结论

快速排序：

平均：

O (n lo g_{2} n)

最坏：

O (n^{2})

平均空间：

O (lo g_{2} n)

最坏空间：

O (n)

不稳定
适用于顺序存储
每次 Partition 至少确定一个枢轴最终位置

资料将其描述为平均性能非常优秀的内部排序方法。

十七、8.4 选择排序

统一思想：

每趟从未排序区中“选”出最小或最大的元素。

主要：

简单选择排序
堆排序

十八、简单选择排序

例如：

5, 2, 4, 1

第一趟，从全部元素找最小：

1

把 $1$ 和第一个位置交换：

1, 2, 4, 5

第二趟在：

2, 4, 5

中找最小。

最重要性质

不管原序列：

已经有序
完全逆序
随机

每一趟还是必须把后面的元素全看一遍才能知道谁最小。

所以比较次数始终：

(n - 1) + (n - 2) + \dots + 1

即：

\frac{n ( n - 1 )}{2}

因此无论最好、平均、最坏：

O (n^{2})

空间：

O (1)

不稳定。

十九、堆排序 ★★★★★

这一部分一定要和第五章的完全二叉树知识联系起来。

堆本质上是：

用数组存储的完全二叉树，并满足父子大小关系。

二十、大根堆与小根堆

大根堆：

A [i] \geq A [2 i]

并且：

A [i] \geq A [2 i + 1]

因此：

每个父亲都不小于孩子。

所以根：

A [1]

是整个堆的最大值。

小根堆反过来。

二十一、数组与完全二叉树的对应

如果结点下标是：

i

那么：

左孩子：

2 i

右孩子：

2 i + 1

双亲：

⌊ \frac{i}{2} ⌋

最后一个非叶结点：

⌊ \frac{n}{2} ⌋

这正是为什么建堆从：

⌊ \frac{n}{2} ⌋

开始。

二十二、建大根堆怎么做？

核心：

从最后一个非叶结点开始，一路向前进行“向下调整”。

代码框架：

for (i = n / 2; i > 0; i--)
    HeapAdjust(A, i, n);

为什么不能从根开始？

因为向下调整有一个隐含前提：

当前结点的左右子树已经是堆。

所以先处理底部。

二十三、HeapAdjust 向下调整

假设：

        20
       /  \
     50    40

这显然不是大根堆。

先在左右孩子中选较大的：

max (50, 40) = 50

发现：

50 > 20

于是 $50$ 上移：

        50
       /  \
     20    40

然后继续对 $20$ 所在子树检查。

因此口诀：

大根堆：孩子先选大，父亲比不过就下沉。

小根堆相反：

孩子先选小。

资料中的 HeapAdjust() 正是沿较大的孩子一路向下筛。建堆总时间复杂度不是 $O (n lo g n)$ ，而是：

O (n)

这是非常常考的结论。

二十四、堆排序真正过程

若想得到升序：

构造大根堆。

因为最大的元素要放最后。

第一步：

构造大根堆

于是：

A [1]

是最大值。

第二步：

交换：

A [1] \leftrightarrow A [n]

最大值到最终位置。

第三步：

只对：

A [1 \dots n - 1]

重新调整成大根堆。

重复。

所以算法：

建大根堆
↓
堆顶 ↔ 最后一个元素
↓
堆长度 - 1
↓
向下调整
↓
再次交换
……

资料中的完整框架就是：

BuildMaxHeap(A, len);

for (i = len; i > 1; i--) {
    Swap(A[i], A[1]);
    HeapAdjust(A, 1, i - 1);
}

二十五、堆排序复杂度

初始建堆：

O (n)

之后需要输出：

n - 1

次。

每次重新调整：

O (lo g_{2} n)

所以：

O (n) + O (n lo g_{2} n)

最终：

O (n lo g_{2} n)

并且最好、平均、最坏均为：

O (n lo g_{2} n)

空间：

O (1)

不稳定。

这就是堆排序相较快排的一大优势：

不会退化成 $O (n^{2})$ 。

二十六、Top-K：堆的超级重要应用

资料还专门提到了新考点：

从海量数据中选最大的 $k$ 个。

比如：

1 亿个数里找最大的 100 个。

不能直接全部排序。

建立大小：

k = 100

的小根堆。

为什么是小根堆？

因为我们维护的是“目前最大的 100 个数”，其中：

最没资格留下来的，就是这 100 个里面最小的那个。

它正好位于小根堆堆顶。

对新数 $x$ ：

若：

x \leq heapTop

丢掉。

若：

x > heapTop

替换堆顶并调整。

最终复杂度：

O (n lo g_{2} k)

空间：

O (k)

反过来：

找最小 $k$ 个数 → 建大根堆。

这个经常考反。

二十七、8.5 归并排序 ★★★★★

归并排序核心不是交换，而是：

把两个已有序序列合成一个更大的有序序列。

二十八、二路归并

两个有序序列：

1, 4, 7

和：

2, 3, 9

两个指针分别指向头部。

比较：

1 < 2

输出 $1$ 。

再比较：

4 > 2

输出 $2$ 。

再：

4 > 3

输出 $3$ 。

最终：

1, 2, 3, 4, 7, 9

本质就是：

两个指针
谁小谁走
某一边空了
另一边整体接上

二十九、归并排序完整思想

最开始每个元素自身都是一个长度为 $1$ 的有序段：

[49] [38] [65] [97] [76] [13] [27]

第一趟：

[38 49] [65 97] [13 76] [27]

第二趟：

[38 49 65 97] [13 27 76]

第三趟：

[13 27 38 49 65 76 97]

三十、归并排序为什么是 $O (n lo g n)$ ？

每一层归并，所有元素都处理一次：

O (n)

从长度 $1$ ：

1 \to 2 \to 4 \to 8 \to \dots \to n

需要：

⌈ lo g_{2} n ⌉

层。

因此：

T (n) = O (n lo g_{2} n)

特别重要：

最好：

O (n lo g_{2} n)

平均：

O (n lo g_{2} n)

最坏：

O (n lo g_{2} n)

它和输入初态基本无关。

三十一、归并排序为什么需要 $O (n)$ 空间？

因为两个有序段合并时，通常需要辅助数组：

B [1 \dots n]

把结果暂存。

因此：

S (n) = O (n)

这也是它与堆排序的重要区别。

三十二、归并排序为什么稳定？

假设：

左段：

4 9_{1}

右段：

4 9_{2}

比较：

4 9_{1} = 4 9_{2}

规定：

相等时优先取左段。

于是：

4 9_{1}

仍在：

4 9_{2}

前。

所以稳定。

三十三、快排与归并最容易混淆的地方

两者都是分治，但区别非常大。

快排

先：

划分

再递归。

核心工作在“分”。

Partition
→ QuickSort(left)
→ QuickSort(right)

归并

先递归分解，再：

合并

核心工作在“合”。

MergeSort(left)
MergeSort(right)
→ Merge

所以可以记：

快排：先干活再递归。

归并：先递归再干活。

三十四、8.5.2 基数排序

基数排序很特殊。

前面的快速、堆、归并等本质上都高度依赖：

a < b ?

而基数排序：

不直接进行关键字之间的大小比较。

例如：

278, 109, 063, 930, \dots

可以从个位开始。

LSD：最低位优先

先按个位分桶。

例如十进制：

r = 10

建立：

Q0
Q1
Q2
...
Q9

数字末位是多少，就放哪个队列。

第一轮：

按个位分配 → 收集。

第二轮：

按十位分配 → 收集。

第三轮：

按百位分配 → 收集。

最后整体有序。

资料把过程概括成两步：

分配

若当前位：

k

则进入：

Q_{k}

收集

依次连接：

Q_{0}, Q_{1}, \dots, Q_{r - 1}

而且每一位的排序都必须稳定。

基数排序复杂度

设：

$n$ ：元素个数
$d$ ：关键字位数
$r$ ：基数，例如十进制 $r = 10$

每一趟：

分配：

O (n)

收集：

O (r)

共 $d$ 趟：

O (d (n + r))

空间：

O (r)

稳定。

而且时间复杂度基本不取决于原序列是否有序。

三十五、计数排序：非大纲但思想值得知道

资料特别说明：

计数排序本身不在当前统考考纲正式范围内，但其思想在历年算法题中出现过。

本质：

对于元素 $x$ ，统计：

# {y ∣ y < x}

假设有 8 个元素小于 $x$ ，那么 $x$ 应放在第：

9

个位置。

或者对整数值域计数：

C[x] = x出现次数

适合：

数据值域较小。

理解即可，不是本章复习的第一优先级。

三十六、8.6 各种内部排序算法比较 ★★★★★

这是整章选择题的核心。

资料的汇总表如下。

排序算法	最好	平均	最坏	空间	稳定
直接插入	$O (n)$	$O (n^{2})$	$O (n^{2})$	$O (1)$	是
折半插入	—	$O (n^{2})$	$O (n^{2})$	$O (1)$	是
冒泡	$O (n)$	$O (n^{2})$	$O (n^{2})$	$O (1)$	是
简单选择	$O (n^{2})$	$O (n^{2})$	$O (n^{2})$	$O (1)$	否
希尔	与增量有关	与增量有关	可到 $O (n^{2})$	$O (1)$	否
快速	$O (n lo g n)$	$O (n lo g n)$	$O (n^{2})$	平均 $O (lo g n)$	否
堆	$O (n lo g n)$	$O (n lo g n)$	$O (n lo g n)$	$O (1)$	否
二路归并	$O (n lo g n)$	$O (n lo g n)$	$O (n lo g n)$	$O (n)$	是
基数	$O (d (n + r))$	同左	同左	$O (r)$	是

三十七、几个横向比较一定要会

1. 哪些受初始序列影响很明显？

直接插入：

很明显。

冒泡：

很明显。

快速：

非常明显。

简单选择：

比较次数基本不受影响。

堆：

渐近复杂度不变。

归并：

基本不影响复杂度。

基数：

趟数由关键字位数决定。

三十八、哪些每趟能确定最终位置？

冒泡

每趟至少一个。

简单选择

每趟一个。

堆排序

每次输出一个堆顶，确定一个。

快排

一次划分：

至少枢轴确定最终位置。

资料明确将这类“中间过程特征”列为考点。

三十九、哪些只适合顺序存储？

资料归纳：

折半插入
希尔
快速
堆

更适合/要求顺序存储。

而：

直接插入
冒泡
简单选择
归并
基数

可以用于链式结构。

其中最容易理解的是堆：

因为堆需要快速求：

2 i, 2 i + 1

所以数组非常自然。

四十、排序算法怎么选？★★★★★

资料专门给出了选择规则。

场景 1： $n$ 很小

直接插入、简单选择。

如果记录本身非常大，交换/移动记录代价高，则简单选择的移动次数比较少。

场景 2：基本有序

优先：

直接插入
冒泡

因为最好：

O (n)

场景 3：数据量大，要求平均速度快

快速排序。

平均：

O (n lo g n)

通常常数较小、实际表现优秀。

场景 4：必须保证最坏也 $O (n lo g n)$ ，而且空间少

堆排序。

时间：

O (n lo g n)

空间：

O (1)

缺点：

不稳定。

场景 5：要求稳定，同时要求 $O (n lo g n)$

归并排序。

这是非常经典的题。

场景 6：关键字位数固定、数量巨大

基数排序。

可以接近线性时间。

四十一、比较排序的理论下界

这是一个重要理论结论。

对于基于比较的排序：

每次比较只有两种结果。

因此整个排序过程可以表示成一棵判定树。

$n$ 个不同元素共有：

n!

种排列。

所以判定树至少有：

n!

个叶子。

树高至少：

lo g_{2} (n!)

根据 Stirling 公式，其数量级为：

Θ (n lo g n)

所以：

任何基于比较的排序，最坏情况下不可能突破 Ω (n lo g n)

这就是为什么基数排序、计数排序能做到接近：

O (n)

因为它们：

不是比较排序。

资料也将该结论列入排序算法选型总结。

四十二、8.7 外部排序 ★★★★

这一部分概念很多，但底层逻辑其实只有一个：

数据太大，内存装不下。

例如一个：

100 GB

的文件，但机器只有：

8 GB

内存。

不能直接：

全部读进内存 → QuickSort

所以必须：

磁盘
↕
内存

不断交换数据。

而磁盘 I/O 比内存比较慢得多，因此资料明确指出：

外部排序性能的主要矛盾是减少磁盘读写次数。

四十三、外部排序基本流程

主要两个阶段：

第一阶段：生成初始归并段

假设内存一次能放 100 万条记录。

读：

前100万条

内部排序后写回磁盘：

R1

再读下一批：

R2

最终得到：

R1 R2 R3 R4 ...

它们各自内部有序。

这些叫：

初始归并段 / 顺串。

第二阶段：多路归并

比如有：

R_{1}, R_{2}, \dots, R_{8}

进行二路归并：

第一趟：

R1 + R2 → R1'
R3 + R4 → R2'
R5 + R6 → R3'
R7 + R8 → R4'

第二趟：

R1' + R2' → R1''
R3' + R4' → R2''

第三趟：

R1'' + R2'' → 最终文件

四十四、归并趟数公式 ★★★★★

若有：

r

个初始归并段。

采用：

k

路归并。

归并趟数：

S = ⌈ lo g_{k} r ⌉

这公式必须会。

例如：

r = 8, k = 2

则：

S = lo g_{2} 8 = 3

如果：

k = 4

则：

S = ⌈ lo g_{4} 8 ⌉ = 2

所以减少归并趟数有两个方向：

增大 k

或：

减小 r

四十五、败者树：解决什么问题？★★★★★

既然增加归并路数：

k

可以降低归并趟数，那是不是：

$k$ 越大越好？

普通 $k$ 路归并中，每次要从 $k$ 个元素中找最小元素。

朴素方法需要约：

k - 1

次比较。

如果 $k$ 很大，内部比较代价也很大。

于是引入：

败者树。

四十六、败者树本质是什么？

可以把它想成：

淘汰赛。

比如 8 个归并段各拿出一个当前最小元素：

R1: 3
R2: 7
R3: 2
R4: 8
...

两两比赛。

关键字小的：

胜者，继续向上。

大的：

败者，留在内部结点。

最终根附近得到全局最小者。

输出这个元素后：

只有它所在那一路读取一个新元素。

于是只需要沿着该叶子到根的一条路径重新比赛。

每次选择的比较次数约：

⌈ lo g_{2} k ⌉

而不是：

k - 1

四十七、为什么叫“败者树”？

与普通锦标赛树最大的区别：

内部结点记录的是输掉比赛的人。

胜者继续向上。

这样更新一个叶子后，只需沿原路径重新比较，特别适合连续不断执行：

“从 $k$ 个输入段当前元素中选最小者”。

这正是多路归并的需求。

四十八、归并路数也不是无限大

资料特别提醒：

$k$ 并不是越大越好。

因为 $k$ 越大，需要的：

输入缓冲区

越多。

如果总内存固定：

每个缓冲区容量下降

于是缓冲区更容易空：

频繁磁盘读取

可能导致 I/O 次数重新上升。

所以正确结论：

在内存条件允许范围内适当提高归并路数。

不是：

“归并路数越大一定越好”。

四十九、置换-选择排序 ★★★★

刚才减少归并趟数还有另一条路：

减少初始归并段数量 r

而：

r \approx \frac{n}{初始归并段长度}

所以办法是：

让每个初始归并段更长。

这就是置换-选择排序。

五十、置换-选择排序怎么工作？

假设内存工作区：

W A

只能装：

w

个记录。

普通方法：

每个初始归并段长度最多约为 $w$ 。

置换-选择不同。

步骤：

读入 $w$ 个记录；
输出当前最小值 MINIMAX；
从磁盘补一个新元素；
只能从：

\geq MINIMAX

的元素中继续选最小值； 5. 如果工作区再也没有能接在当前归并段后面的元素，则当前归并段结束； 6. 剩余元素进入下一归并段。

一个关键理解

假设刚刚输出：

44

那当前归并段必须保持升序。

接下来读进：

10

显然：

10 < 44

所以它：

不能再属于当前归并段。

它被“冻结”起来，留到下一归并段。

而如果读进：

56

因为：

56 \geq 44

它还能继续参加当前段。

这就是整个算法最核心的逻辑。

五十一、置换-选择为什么有用？

初始归并段长度可以：

超过内存工作区容量。

对于随机输入，配套模拟资料给出的经典结论是：

平均初始归并段长度约为工作区大小的两倍。

如果工作区：

w

平均段长度约：

2 w

因此归并段数量：

r

大约减半。

归并趟数：

S = ⌈ lo g_{k} r ⌉

自然下降。

五十二、最佳归并树 ★★★★

置换-选择以后有个新问题：

初始归并段长度可能不同。

比如：

9, 30, 12, 18, 3, 17, 2, 6, 24

应该先归并哪些？

如果乱归并：

很长的归并段可能被反复读写很多次。

导致大量 I/O。

因此希望：

小段多归并几次，大段少归并几次。

这跟哈夫曼树完全一样。

所以：

最佳归并树本质就是 $k$ 叉哈夫曼树。

五十三、为什么 WPL 对应 I/O？

设某初始归并段长度：

w_{i}

它参与：

l_{i}

次归并。

那么这些记录需要被处理：

w_{i} l_{i}

次。

全部加起来：

WPL = i \sum w_{i} l_{i}

它对应整个归并过程中记录读取量。

又因为一次归并通常：

读一次 + 写一次。

所以总 I/O 与：

2 \times WPL

五十四、虚段为什么存在？★★★★★

这是外部排序里非常容易觉得抽象的知识。

如果要构造严格的 $k$ 叉树，叶子数不能随便取。

严格 $k$ 叉树中：

n_{0} = (k - 1) n_{k} + 1

因此：

n_{k} = \frac{n _{0} - 1}{k - 1}

如果：

\frac{n _{0} - 1}{k - 1}

不是整数，就说明当前初始归并段数量不能恰好组成严格 $k$ 叉树。

于是补：

权值为 $0$ 的虚段。

五十五、虚段个数怎么算？

设：

u = (n_{0} - 1) mod (k - 1)

如果：

u = 0

无需虚段。

如果：

u \neq = 0

需要补：

k - u - 1

个虚段。

也可以理解成：

补到满足

(n_{0}^{'} - 1) mod (k - 1) = 0

为止。

例如：

n_{0} = 8, k = 3

则：

(8 - 1) mod (3 - 1) = 7 mod 2 = 1

所以补：

3 - 1 - 1 = 1

个虚段。

得到：

9

个叶结点。

此时：

(9 - 1) mod 2 = 0

可以构成严格三叉树。

五十六、本章最容易出的“陷阱”

最后把高频错误集中解决。

错误 1

折半插入排序是 $O (n lo g n)$ 。

错。

因为：

比较减少

但：

移动仍为 O (n^{2})

所以总时间仍：

O (n^{2})

错误 2

快速排序任何情况下都最快。

错。

最坏：

O (n^{2})

资料配套题也明确把“快速排序时间性能最佳”作为错误表述。

错误 3

有序序列对快速排序最好。

如果固定取首元素为枢轴：

恰恰可能最坏。

错误 4

建堆需要 $O (n lo g n)$ 。

错。

整体建堆：

O (n)

单次调整才是：

O (lo g n)

错误 5

堆排序升序应该使用小根堆。

一般经典原地实现中恰好相反：

升序：

大根堆

因为不断把最大元素放到数组尾部。

错误 6

归并排序空间复杂度 $O (lo g n)$ 。

错。

递归栈虽约：

O (lo g n)

但辅助数组：

O (n)

占主导。

所以：

O (n)

错误 7

所有 $O (n lo g n)$ 排序都不稳定。

错。

归并排序：

O (n lo g n)

而且稳定。

错误 8

基数排序突破 $n lo g n$ 下界，所以比较排序下界是错的。

错。

Ω (n lo g n)

限制的是：

基于关键字比较的排序。

基数排序不是比较排序。

错误 9

外部排序主要优化 CPU 比较次数。

错。

最主要的是：

减少外存 I/O

错误 10

$k$ 路归并的 $k$ 越大一定越快。

错。

增大 $k$ 能降低：

S = ⌈ lo g_{k} r ⌉

但会占用更多输入缓冲区；内存固定时缓冲区变小，可能导致更多 I/O。

五十七、最后给出一张 408 必背总表

算法	核心动作	最好	平均	最坏	空间	稳定	每趟确定最终位置
直接插入	插入有序区	$O (n)$	$O (n^{2})$	$O (n^{2})$	$O (1)$	✓	×
折半插入	二分找位置+移动	—	$O (n^{2})$	$O (n^{2})$	$O (1)$	✓	×
希尔	缩小增量插入	与增量有关	与增量有关	可 $O (n^{2})$	$O (1)$	×	×
冒泡	相邻交换	$O (n)$	$O (n^{2})$	$O (n^{2})$	$O (1)$	✓	✓
快速	Partition	$O (n lo g n)$	$O (n lo g n)$	$O (n^{2})$	平均 $O (lo g n)$	×	枢轴
简单选择	选最小	$O (n^{2})$	$O (n^{2})$	$O (n^{2})$	$O (1)$	×	✓
堆排序	堆顶交换+调整	$O (n lo g n)$	$O (n lo g n)$	$O (n lo g n)$	$O (1)$	×	✓
归并	合并有序段	$O (n lo g n)$	$O (n lo g n)$	$O (n lo g n)$	$O (n)$	✓	×
基数	分配+收集	$O (d (n + r))$	同	同	$O (r)$	✓	×

这张表和资料中的排序算法比较部分基本就是第 8 章选择题最核心的知识集合。

五十八、按考研优先级复习

如果按“最值得投入时间”的顺序，建议这一章这样掌握：

第一梯队：必须能手算、能看代码、能分析

快速排序
- 一趟 Partition
- 中间结果
- 最好/最坏情况
- 递归深度
- 枢轴最终位置
堆排序
- 大/小根堆判断
- 建堆
- 向下调整
- 删除堆顶
- 插入
- Top-K
归并排序
- 二路归并
- 递归结构
- 趟数
- 比较次数
- 稳定性

第二梯队：选择题必须熟练

直接插入
折半插入
希尔
冒泡
简单选择
各算法稳定性、复杂度、存储方式、过程特征

第三梯队：外部排序专项

要抓住这一条逻辑链：

减少 I/O

于是：

S = ⌈ lo g_{k} r ⌉

所以：

提高 k \Rightarrow 败者树

而：

降低 r \Rightarrow 置换 - 选择

产生不等长归并段以后：

\Rightarrow 最佳归并树

不能构成严格 $k$ 叉树：

\Rightarrow 补虚段

这样外部排序看似五六个概念，实际上是一条非常完整的因果链。

如果把这一章真正学到“看到任意一个序列，都能手算快速排序一趟、建大根堆和一次堆调整、二路归并一趟、希尔给定增量的一趟、基数分配收集、置换选择初始段”，那么第 8 章绝大多数 408 选择题就已经进入比较稳的状态了。

第 8 章 排序

On this page