第8章 排序 自学版

章节定位：综合收束章

• 这一章把内部排序、非比较型排序和外部排序整合成“过程 + 性质 + 适用场景”的总比较框架。
• 建议先理解每类排序的核心动作，再做稳定性、复杂度和外部排序归并过程的综合对照。

1. 本章定位

第 8 章是整本书里“最容易一口气学很多算法名字，但最容易越学越乱”的一章。

表面上它讲的是：

1. 直接插入排序
2. 冒泡排序
3. 快速排序
4. 选择排序
5. 堆排序
6. 归并排序
7. 计数排序
8. 基数排序
9. 外部排序

但真正主线不是“把名字背下来”，而是：

这些排序算法到底是通过什么动作，让序列一步步变得更有序。

如果这条主线不抓住，学生很容易学成：

1. 会背时间复杂度
2. 会背稳定性
3. 但一看到代码就断线

所以这一章我们会始终盯住三个问题：

1. 每种排序的核心动作是什么
2. 它为什么会快或会慢
3. 它适合什么场景，容易错在哪里

2. 学习目标

学完第 8 章后，建议至少达到下面这些目标：

1. 能分清插入、交换、选择、归并、分配这几类排序思想。
2. 能理解稳定性、时间复杂度、空间复杂度在排序里的真实含义。
3. 能看懂并写出常见内部排序算法的真实 C 代码。
4. 能比较直接插入排序、冒泡排序、快速排序、堆排序、归并排序的优缺点。
5. 能理解计数排序、基数排序为什么不完全依赖关键字比较。
6. 能说清外部排序为什么要和磁盘 / 文件块联系起来理解。

3. 前置知识

继续往下看之前，最好已经比较稳地掌握：

1. 本书第2章正文 中的顺序表和数组下标操作。
2. 本书第5章正文 中的完全二叉树概念。
3. 递归、分治、辅助数组这些常见代码组织方式。

这一章和前面章节的衔接关系很强：

1. 堆排序和完全二叉树密切相关。
2. 归并排序和分治思想密切相关。
3. 快速排序和递归划分密切相关。
4. 计数排序、基数排序和第 7 章中“用结构换效率”的思路也有呼应。

4. 本章结构总览

第 8 章可以按下面的顺序理解：

1. 先抓排序的基本概念和评价指标。
2. 再看插入类排序。
3. 再看交换类排序。
4. 再看选择类排序。
5. 再看归并、计数、基数这些“更偏结构化处理”的排序。
6. 最后再看各种内部排序的比较和外部排序。

5. 8.1 排序的基本概念

5.1 什么叫排序

排序就是：

1. 把一组记录
2. 按关键字
3. 调整成递增或递减次序

真正要抓的是：

1. 比较的是“关键字”
2. 调整的是“记录位置”

5.2 稳定性为什么重要

稳定性指的是：

1. 如果两个记录关键字相同
2. 排序前谁在前面
3. 排序后仍然谁在前面

这件事在单独一趟排序里看起来没那么显眼，但在：

1. 多关键字排序
2. 业务数据排序
3. 基数排序的多趟分配

这些场景里会非常重要。

5.3 内部排序和外部排序

这一章前面大部分算法都属于内部排序：

1. 数据基本都在内存里
2. 重点优化比较和移动

而外部排序的重点则是：

1. 数据量很大
2. 需要频繁访问磁盘
3. 要尽量减少 I/O 和归并趟数

6. 8.2 插入排序

6.1 直接插入排序的核心直觉

直接插入排序最适合的理解方式是：

1. 把序列前面一段看成“已经排好”
2. 每次拿一个新元素
3. 往已排序区里插进去

它像在整理手里的扑克牌：

1. 前面的牌已经排好了
2. 新抓来一张
3. 找到它应该插入的位置

6.2 折半插入排序

折半插入排序不是把“移动次数”减半，而是：

1. 用折半查找更快地找到插入位置
2. 但元素移动次数通常并不会因此消失

所以它优化的是：

1. 定位插入位置的比较过程

而不是：

1. 后移元素的成本

7. 8.3 交换排序

7.1 冒泡排序

冒泡排序最直观：

1. 相邻元素比较
2. 逆序就交换
3. 每一趟把一个较大元素“冒”到后面

它代码不难，但很适合作为：

1. 稳定性
2. 提前结束优化
3. 排序趟数

这些概念的练习入口。

7.2 快速排序

快速排序的核心动作是：

1. 选一个枢轴
2. 划分序列
3. 让左边都不大于它，右边都不小于它
4. 再递归处理左右两边

这是一种非常典型的分治算法。

8. 8.4 选择排序

8.1 简单选择排序

它每一趟做的事情很固定：

1. 在未排序部分里找最小值
2. 把它放到当前应在的位置

它的优点是交换次数少，思路直。

8.2 堆排序

堆排序最该抓的是：

1. 它不是简单“挑最值”
2. 而是先把序列组织成堆
3. 再反复取堆顶最大值

所以堆排序的关键不是“排序过程”本身，而是：

建堆 + 调整堆

9. 8.5 归并排序、计数排序和基数排序

9.1 归并排序

归并排序的核心动作是：

1. 先分
2. 再治
3. 最后把两个有序段归并成一个有序段

它的优势是思路稳定、复杂度稳定。

9.2 计数排序和基数排序

这两类排序特别值得和前面的“比较型排序”区分开。

它们更像是：

1. 借助关键字范围或位数结构
2. 减少直接比较带来的成本

所以它们的思路更偏“结构化分配与收集”。

10. 8.6 各种内部排序算法的比较及应用

这一部分后面会重点补：

1. 时间复杂度比较
2. 空间复杂度比较
3. 稳定性比较
4. 适用场景比较

11. 8.7 外部排序

这一部分后面会重点补：

1. 为什么内存放不下就要考虑外部排序
2. 为什么外部排序的核心不再只是比较次数
3. 为什么多路归并和败者树这类结构会出现

12. 第8章代码阅读入口

第 8 章第一版代码目前已经先落了最值得优先掌握的内部排序算法：

1. 直接插入排序
2. 冒泡排序
3. 快速排序
4. 简单选择排序
5. 堆排序
6. 归并排序
7. 计数排序

建议阅读顺序：

1. 先看 InsertSort
2. 再看 BubbleSort
3. 再看 SelectionSort
4. 再看 QuickSort
5. 再看 HeapSort
6. 最后看 MergeSort 和 CountingSort

对应代码文件：

• 第8章普通代码版

16. 当前边界说明

这一版是“第 8 章启动版”，不是终版。

目前先把最适合直接代码落地、也最适合先学的内部排序部分起起来了。

还没有做厚的部分主要是：

1. 各种排序算法的题型索引
2. 原书试题区整理
3. 外部排序的完整讲解
4. 基数排序和外部排序的更完整代码专项

这些会在后续轮次继续补上。

16. 8.2 和 8.3 重点展开

16.1 直接插入排序为什么适合做“排序直觉起点”

直接插入排序很适合作为排序学习的第一站，因为它最像人在手工整理东西。

你可以把它想成整理扑克牌：

1. 左手里前面几张牌已经排好了
2. 新来一张牌
3. 找到它该插进去的位置
4. 把后面的牌整体往后挪一格

这个过程特别值得学生先看懂，因为后面很多排序题的理解都离不开这两件事：

1. 怎么找到“该放的位置”
2. 怎么把元素移动过去

16.2 直接插入排序的核心动作到底是什么

直接插入排序每一趟真正做的事，其实只有三步：

1. 取出当前待插入元素
2. 在已排序区中从后往前找位置
3. 把比它大的元素整体后移

所以它的本质不是“交换”，而是：

插入前先挪空位。

这也是它和冒泡排序最容易混但其实最不一样的地方：

1. 冒泡排序主要靠交换
2. 直接插入排序主要靠后移 + 插入

16.3 直接插入排序：原书思路版伪代码

InsertSort(A, n)
    for i = 1 to n - 1
        temp = A[i]
        j = i - 1
        while j >= 0 and A[j] > temp
            A[j + 1] = A[j]
            j = j - 1
        A[j + 1] = temp

学生看这段伪代码时，最该抓住的是：

1. temp 为什么要先存下来
2. 为什么比较时是从后往前扫
3. 为什么最后插回的是 j + 1

16.4 直接插入排序：对应真实代码

当前真实代码位置：

• 第8章普通代码版（约第31行）

对应函数：

• InsertSort

这段代码和伪代码高度对应，很适合训练“从教材算法到真实代码”的转换能力。

尤其要注意：

1. temp 保存当前待插入元素
2. j 从已排序区尾部开始回退
3. 回退过程中更大的元素整体后移
4. 最后再把 temp 放进空出来的位置

16.5 直接插入排序的复杂度和稳定性怎么理解

这类题不能只背结论，最好要有直觉。

时间复杂度：

1. 最好情况：原序列本来就接近有序
2. 最坏情况：序列完全逆序，每次都要大范围后移

所以它在“基本有序”场景下往往表现不错。

稳定性：

1. 它是稳定的
2. 因为相等元素通常不会被后来的相等元素跨过去

这条稳定性后面和选择排序、快速排序做对比时很重要。

16.6 折半插入排序到底优化了什么

这一点特别容易考判断题。

折半插入排序优化的是：

1. 找插入位置时的比较过程

它没有本质优化的是：

1. 元素后移次数

所以你要明确区分：

1. 比较次数减少了
2. 但移动次数不一定显著减少

这就是为什么折半插入排序听起来更高级，但在整体复杂度层面并不会神奇地变成对数级排序。

16.7 冒泡排序为什么看起来简单却仍值得学

很多学生会觉得冒泡排序“太基础，不值一学”，但它很适合用来练这些东西：

1. 排序趟数
2. 相邻交换
3. 稳定性
4. 提前结束优化

而且很多题就爱考它的这些基础点。

冒泡排序的画面感很强：

1. 每比较一对相邻元素
2. 如果逆序就交换
3. 一趟结束后，一个较大元素会被推到后面

16.8 冒泡排序：原书思路版伪代码

BubbleSort(A, n)
    for i = 0 to n - 2
        flag = false
        for j = 0 to n - 2 - i
            if A[j] > A[j + 1]
                swap(A[j], A[j + 1])
                flag = true
        if flag == false
            break

这段伪代码最该抓的是：

1. 为什么内层循环上界会越来越短
2. flag 为什么能提前结束
3. 为什么说它是稳定排序

16.9 冒泡排序：对应真实代码

当前真实代码位置：

• 第8章普通代码版（约第51行）

对应函数：

• BubbleSort

代码里最值得学生重点盯的是：

1. swapped 标记
2. 每一趟结束后，末尾一段为什么可以不再参与比较

如果这两点看懂了，冒泡排序就不会停留在“会背名字”的层次。

16.10 冒泡排序的提前结束为什么重要

这条优化特别容易在选择题里出现。

如果某一趟扫描下来：

1. 一次交换都没有发生
2. 说明当前序列已经有序
3. 后面就没必要继续做剩余趟数

所以 flag 的价值不是“代码更好看”，而是：

避免对已经有序的序列做多余工作。

16.11 快速排序最该抓的是“划分”

快速排序最容易学乱，因为学生经常把注意力全放在递归上。

但它真正的灵魂不在“递归”两个字，而在：

划分之后，枢轴左边都不大于它，右边都不小于它。

只要划分这一步看懂了，快速排序后面的递归其实就是自然展开。

16.12 快速排序：原书思路版伪代码

QuickSort(A, low, high)
    if low < high
        pivotpos = Partition(A, low, high)
        QuickSort(A, low, pivotpos - 1)
        QuickSort(A, pivotpos + 1, high)

其中关键是：

Partition(A, low, high)
    pivot = A[low]
    从两端向中间扫描
    把小元素放左边，大元素放右边
    最后把 pivot 放回正确位置
    return pivot 的最终位置

真正要学会的是：

1. 枢轴不是“随便换来换去”
2. 划分完成后，枢轴位置就确定了
3. 后面递归时不再动这个位置

16.13 快速排序：对应真实代码

当前真实代码位置：

1. 划分函数：
2. 第8章普通代码版（约第95行）
3. 快速排序本体：
4. 第8章普通代码版（约第118行）

对应函数：

1. Partition
2. QuickSort

学生看这段代码时最容易卡住的是：

1. low 和 high 为什么都在动
2. 为什么不是每次都显式交换
3. 为什么最后一定要把 pivot 放回 array[low]

所以这块后面非常适合做逐行拆解。

16.14 快速排序为什么平均快、但最坏会变差

这是快速排序最经典的理解点。

如果每次划分都比较均匀：

1. 左右子区间规模差不多
2. 递归树高度较低
3. 整体效率会很好

但如果每次划分都特别不均匀，比如：

1. 每次都把最小值或最大值当枢轴
2. 导致一边几乎空，另一边几乎是全部元素

那快速排序就会退化得很厉害。

所以快速排序的关键，不只是“分”，而是：

分得是否均匀。

16.15 8.2 和 8.3 的高频易错点

这一部分当前最容易错的地方主要有：

1. 把直接插入排序和冒泡排序混成一类“反正都在换位置”
2. 折半插入排序时误以为移动次数也变成对数级
3. 冒泡排序忘记 flag 提前结束优化
4. 快速排序把“递归”当重点，却没看懂 Partition
5. 快速排序划分后，错误地继续把枢轴所在位置也递归进去
6. 快速排序最坏情况为什么会差，解释不清

17. 8.4 重点展开

17.1 简单选择排序最该抓的不是“交换”，而是“选最小”

简单选择排序和冒泡排序看起来都在换位置，所以学生很容易把它们混在一起。

但它们真正的核心动作完全不同：

1. 冒泡排序是不断比较相邻元素，逆序就交换
2. 简单选择排序是每一趟先在未排序区里找最小值，再一次性放到前面

所以选择排序更像：

1. 先巡视一遍
2. 确定谁最小
3. 再把它换到当前该在的位置

17.2 简单选择排序每一趟到底在做什么

每一趟固定做三件事：

1. 把当前起点位置当成“暂时最小值位置”
2. 在后面的未排序区继续扫描
3. 找到真正最小值后，再和当前起点交换

所以它和直接插入排序最大的区别是：

1. 直接插入排序是在已排序区里给新元素找位置
2. 简单选择排序是在未排序区里给当前位置找最小元素

17.3 简单选择排序：原书思路版伪代码

SelectionSort(A, n)
    for i = 0 to n - 2
        min = i
        for j = i + 1 to n - 1
            if A[j] < A[min]
                min = j
        if min != i
            swap(A[i], A[min])

看这段伪代码时，最该抓的是：

1. min 记录的是“当前最小元素的位置”
2. 内层循环不是在做交换，而是在找更小的值
3. 真正交换通常一趟只发生一次

17.4 简单选择排序：对应真实代码

当前真实代码位置：

• 第8章普通代码版（约第75行）

对应函数：

• SelectionSort

这段代码里最值得学生盯住的是：

1. min_index 的更新过程
2. 为什么扫描完后才交换
3. 为什么说它“交换次数少”，但比较次数并不一定少

17.5 简单选择排序的稳定性为什么容易错

这条很容易出判断题。

简单选择排序通常是不稳定的。

原因不是它一定大量交换，而是：

1. 它在后面找到最小元素后
2. 直接和前面当前位置交换
3. 这个动作可能让相等关键字的相对次序发生变化

所以学生最容易掉坑的地方是：

1. 看到它“一趟最多交换一次”
2. 就误以为它稳定

但稳定性不看交换次数多少，而看：

相等元素的前后关系会不会被改变。

17.6 堆排序为什么看起来像“选择排序的升级版”

堆排序和简单选择排序之间有一个很值得学生抓住的联系：

1. 它们都在不断把当前最值放到合适位置

区别在于：

1. 简单选择排序每一趟都线性扫描去找最小值
2. 堆排序先把序列组织成堆，让最大值直接出现在堆顶

所以堆排序可以理解成：

把“找最值”这件事结构化了。

这就是它比简单选择排序更强的地方。

17.7 堆排序最该抓的是“大根堆 + 下滤”

堆排序真正的核心，不是“交换堆顶和末尾”这个动作，而是：

1. 如何建堆
2. 如何在交换后恢复堆

更准确地说：

1. 先把序列调整成大根堆
2. 让堆顶永远是当前最大值
3. 把堆顶换到当前末尾
4. 再对剩余区间做一次下滤

所以堆排序的灵魂动作其实是：

下滤（SiftDown）

17.8 为什么堆排序和完全二叉树有关系

这一点是堆排序最容易“会写代码但没讲明白”的地方。

堆本质上是一棵完全二叉树，只不过通常用数组存。

所以：

1. 某个下标位置的元素，对应树中一个结点
2. 它的左右孩子位置可以直接通过下标算出来

这也是为什么堆排序代码里会出现类似：

1. 2 * root + 1
2. 2 * root + 2

这样的表达式。

学生如果把这层“数组下标 <-> 完全二叉树位置”看懂，堆排序代码会一下子顺很多。

17.9 堆排序：原书思路版伪代码

HeapSort(A, n)
    BuildMaxHeap(A)
    for i = n - 1 downto 1
        swap(A[0], A[i])
        对 A[0..i-1] 重新做下滤调整

其中最关键的子过程是：

SiftDown(A, start, end)
    让 start 位置的元素向下移动
    直到以它为根的子树重新满足大根堆性质

学生要特别注意：

1. 每次交换堆顶和末尾后，末尾元素已经就位
2. 真正还需要调整的，是前面剩余那部分堆

17.10 堆排序：对应真实代码

当前真实代码位置：

1. 下滤：
2. 第8章普通代码版（约第130行）
3. 堆排序本体：
4. 第8章普通代码版（约第154行）

对应函数：

1. SiftDown
2. HeapSort

看代码时最值得重点盯的是：

1. 为什么总是先找左右孩子中更大的那个
2. 为什么一旦父结点已经不小于较大孩子，就可以停
3. 为什么每次把堆顶换到最后后，要缩小堆的有效范围

17.11 建堆为什么可以从最后一个非叶结点开始

这是堆排序里很经典、也很容易考的点。

原因是：

1. 叶结点本身天然就是堆
2. 不需要再调整
3. 所以真正需要调整的，是那些有孩子的结点
4. 从最后一个非叶结点开始向前做下滤，就能逐步把整棵树变成堆

这条结论如果理解了，学生就不会把建堆误解成“从根开始反复乱调”。

17.12 简单选择排序和堆排序怎么放在一起比较

这一组题非常适合对照记：

1. 简单选择排序
2. 每一趟线性扫描找最值
3. 思路直观
4. 不稳定
5. 堆排序
6. 先把找最值结构化成堆
7. 每次更快地定位当前最大值
8. 通常也不稳定

所以这两类排序虽然都属于“选择排序思想”，但层次完全不同：

1. 一个是直接找
2. 一个是借助堆来找

17.13 8.4 的高频易错点

这一部分当前最容易错的地方主要有：

1. 把简单选择排序和冒泡排序混掉
2. 误以为简单选择排序是稳定的
3. 不理解堆排序里的数组下标为什么对应完全二叉树
4. 只记得堆顶是最大值，却不会解释为什么
5. 不会说明建堆为什么从最后一个非叶结点开始
6. 交换堆顶和末尾后，忘记缩小堆的有效区间

18. 8.5 重点展开

18.1 归并排序最该抓的是“先分后并”

归并排序最容易被学生学成一句空话：分治法。

但真正要抓住的不是“分治”两个字，而是：

1. 先把大问题拆成小问题
2. 先让左右两边各自有序
3. 再把两个有序段合成一个更大的有序段

所以归并排序最核心的动作不是“交换”，而是：

归并两个有序段。

这也是它和快速排序最容易混、但本质很不同的地方：

1. 快速排序靠划分
2. 归并排序靠合并

18.2 归并排序为什么稳定

归并排序通常是稳定的。

更准确地说，稳定性的关键不在“递归”，而在“归并时相等元素怎么处理”。

如果归并两个有序段时：

1. 遇到相等元素
2. 优先取左边那个
3. 那就不会把原有相对次序打乱

这就是为什么代码里常会写成：

1. if (A[i] <= A[j])
2. 而不是只写成严格小于

这一点后面做稳定性比较题时很重要。

18.3 归并排序：原书思路版伪代码

MergeSort(A, left, right)
    if left < right
        mid = (left + right) / 2
        MergeSort(A, left, mid)
        MergeSort(A, mid + 1, right)
        Merge(A, left, mid, right)

关键子过程：

Merge(A, left, mid, right)
    用两个指针分别扫描两个有序段
    每次取较小者放入辅助数组
    最后把剩余元素接上
    再写回原数组

学生看这段时最该抓的是：

1. 递归不是目的，递归只是为了得到两个有序段
2. 真正决定排序效果的，是 Merge

18.4 归并排序：对应真实代码

当前真实代码位置：

1. 归并函数：
2. 第8章普通代码版（约第171行）
3. 递归主体：
4. 第8章普通代码版（约第200行）
5. 外壳函数：
6. 第8章普通代码版（约第214行）

对应函数：

1. Merge
2. MergeSortRecursive
3. MergeSort

学生看这段代码时，最值得重点盯的是：

1. i 和 j 为什么分别指向两个有序段
2. temp 为什么必须存在
3. 为什么合并完后还要再写回原数组

18.5 归并排序为什么通常更稳，但空间开销更大

这一组判断题特别常见。

归并排序的优势在于：

1. 思想稳定
2. 时间复杂度比较稳定
3. 稳定性也较好

但它的代价是：

1. 通常要借助辅助数组
2. 所以空间开销会更高

所以你不能只记“归并排序好”，而要记住：

1. 它是用额外空间换来较稳定的排序过程

18.6 计数排序为什么和前面的排序思路不一样

计数排序特别值得学生从“思想切换”的角度看。

前面的插入、交换、选择、归并，核心都离不开关键字比较。

计数排序则不一样，它更像在做：

1. 统计每个值出现了多少次
2. 再按统计结果重建有序序列

所以它的核心不再是：

1. 谁和谁比大小

而是：

1. 这个值出现了几次

18.7 计数排序适合什么场景

计数排序最适合的不是“所有整数”，而是：

1. 关键字范围不大
2. 且通常是整数
3. 范围已知或容易确定

因为它要开一个“计数数组”。

如果关键字范围特别大，但实际元素很少，那就会出现：

1. 计数数组很大
2. 空间利用很差

所以计数排序不能只看时间快不快，还要看值域是否合适。

18.8 计数排序：原书思路版伪代码

CountingSort(A, n, maxv)
    初始化计数数组 count
    扫描 A，统计每个关键字出现次数
    按关键字从小到大输出到原数组或结果数组

这段伪代码最该抓的是：

1. 它不是通过不断比较来决定次序
2. 而是通过“计数 -> 回填”来得到次序

18.9 计数排序：对应真实代码

当前真实代码位置：

• 第8章普通代码版（约第231行）

对应函数：

• CountingSort

学生看这段代码时最值得重点盯的是：

1. 为什么先把 counts 清零
2. 为什么要先扫描原数组做统计
3. 为什么最后是按计数结果重新写回

18.10 基数排序最该抓的是“按位分配，再按位收集”

基数排序最容易学乱，因为学生经常只记一句“从低位到高位”。

更稳的理解方式是：

1. 先按某一位把元素分到不同桶里
2. 再按桶顺序收集回来
3. 然后继续处理更高一位

所以基数排序的本质不是“整体直接排好”，而是：

一位一位地让序列越来越有序。

18.11 为什么基数排序通常要求稳定

这一点非常关键。

如果在处理某一位时，不稳定：

1. 前面较低位已经建立起来的相对顺序
2. 可能会被后续打乱

所以基数排序通常依赖：

1. 每一趟按位排序必须稳定

这也是为什么教材里常把：

1. 基数排序
2. 稳定分配 / 收集

绑定在一起讲。

18.12 比较型排序和非比较型排序怎么区分

这一组题特别值得单独抓出来。

比较型排序包括：

1. 插入排序
2. 冒泡排序
3. 快速排序
4. 选择排序
5. 堆排序
6. 归并排序

它们的核心都离不开：

1. 比较关键字大小

而计数排序、基数排序更偏：

1. 利用关键字范围或位结构
2. 通过统计、分配、收集得到次序

所以学生最该建立的是这个边界：

1. 不同排序算法，不一定都在“不断比较”

18.13 8.5 的高频易错点

这一部分当前最容易错的地方主要有：

1. 把归并排序和快速排序都简单归成“递归排序”，却说不清差别
2. 归并排序代码里看不懂辅助数组 temp 的作用
3. 误以为计数排序适合所有整数排序问题
4. 只会背基数排序“按位排”，但不理解为什么每一趟必须稳定
5. 把计数排序、基数排序也当成普通比较型排序来理解

19. 8.6 重点展开

19.1 为什么这一节一定要做成“对照表思维”

很多学生学排序时最常见的问题，不是单个算法不会，而是：

1. 每个算法单看好像都懂
2. 一到比较题就开始混
3. 稳定性、复杂度、适用场景全串了

所以 8.6 这一节最重要的任务，不是再讲一遍算法过程，而是：

把前面学过的排序算法放到同一张比较地图里。

只有这样，学生看到题目时才会从：

1. “这是什么排序”
2. 进化到
3. “它为什么适合这个场景”

19.2 各种内部排序最该先比较哪四件事

比较内部排序时，最值得优先抓住四个维度：

1. 时间复杂度
2. 空间复杂度
3. 稳定性
4. 适用场景

这四个维度里，最容易被背成口号的是前两项。

真正更重要的是后两项：

1. 稳定性决定相等关键字的相对次序是否保留
2. 适用场景决定算法“什么时候值得用”

19.3 时间复杂度比较不能只背“最好、平均、最坏”

这一类题最容易学成表格背诵。

但更稳的理解方式是先问：

1. 这个算法的主动作是什么
2. 为什么这个动作在某些情况下会很顺
3. 为什么某些情况下会变差

例如：

1. 直接插入排序
2. 基本有序时很友好
3. 冒泡排序
4. 提前结束时会更轻松
5. 快速排序
6. 划分均匀时很强
7. 划分极不均匀时会恶化
8. 堆排序
9. 表现比较稳
10. 归并排序
11. 复杂度也很稳

所以复杂度不是死记结果，而是要和“为什么会这样”绑定。

19.4 空间复杂度比较最容易在哪掉坑

学生最容易在这两类算法上掉坑：

1. 快速排序
2. 归并排序

原因是：

1. 快速排序看起来在原数组里排，好像很省空间
2. 但递归调用本身也要占栈空间
3. 归并排序则通常直接借助辅助数组

所以做空间复杂度题时，不要只盯“有没有另外开数组”，还要看：

1. 递归栈
2. 辅助数组
3. 是否真正原地

19.5 稳定性最适合怎么记

稳定性如果只靠硬背，很容易把排序算法背混。

更好记的方法是看“相等关键字会不会被强行跨过”。

可以这样理解：

1. 直接插入排序
2. 通常稳定
3. 因为相等元素不会被后来的相等元素越过去
4. 冒泡排序
5. 通常稳定
6. 因为只在严格逆序时交换相邻元素
7. 简单选择排序
8. 通常不稳定
9. 因为后面找到的最小值可能直接换到前面，打乱相等元素次序
10. 快速排序
11. 通常不稳定
12. 因为划分过程中相等元素相对位置可能改变
13. 堆排序
14. 通常不稳定
15. 归并排序
16. 通常稳定，前提是归并时相等元素先取左边

所以稳定性最适合和“元素移动方式”一起记。

19.6 交换次数、移动次数、比较次数要分开看

这一点很容易在综合比较题里出坑。

很多学生一看到：

1. 交换少
2. 就觉得一定更快

但这并不总成立。

更稳的看法是：

1. 比较次数
2. 元素移动次数
3. 交换次数

这三者不是一回事。

例如：

1. 简单选择排序交换次数少
2. 但比较次数并不低

所以做题时一定要看题目到底在比较哪一种代价。

19.7 哪些排序特别适合“基本有序”序列

这一类题很经典。

最值得先想到的是：

1. 直接插入排序

因为它在“基本有序”情况下：

1. 新元素通常不用挪太远
2. 比较和移动都会减少

冒泡排序如果加了提前结束，也会比完全乱序时轻松。

所以这类题不要只会背算法名字，要能说清：

1. 为什么它在基本有序时更占优势

19.8 哪些排序更适合数据量大且要求性能稳定

这一类题最容易让学生在快速排序和归并排序、堆排序之间犹豫。

更稳的思路是：

1. 如果强调平均表现强，常会想到快速排序
2. 如果强调最坏情况下也要稳定，归并排序、堆排序通常更值得关注

但还要继续细分：

1. 归并排序更吃辅助空间
2. 堆排序通常不稳定

所以场景题一定要连着看：

1. 数据规模
2. 稳定性要求
3. 空间限制

19.9 为什么“哪种排序最好”通常是伪问题

这类题特别适合帮学生建立成熟判断。

排序里通常没有脱离场景的“绝对最好”。

更合理的问法应该是：

1. 数据规模多大
2. 是否基本有序
3. 是否要求稳定
4. 是否允许额外空间
5. 是否是整数且值域有限

不同条件下，答案会完全不同。

所以学生到这一节最重要的成长之一，就是从：

1. “背最优算法”
2. 进化到
3. “按场景选算法”

19.10 8.6 高频比较题统一抓法

这一节高频题通常可以归到下面几类：

1. 复杂度比较题
2. 稳定性判断题
3. 空间复杂度判断题
4. 场景选择题
5. 算法分类题
6. 插入类、交换类、选择类、归并类、分配类

做题时建议固定这样走：

1. 先判断题目问的是“性质”还是“场景”
2. 再锁定 2 到 3 个候选算法
3. 最后用稳定性、空间、复杂度去排除

19.11 8.6 当前最容易丢分的点

这一节当前最容易丢分的地方主要有：

1. 只会背复杂度表，不会解释原因
2. 稳定性靠死记，容易把快速排序、堆排序、选择排序混掉
3. 空间复杂度时漏看递归栈
4. 把“交换次数少”和“整体代价低”混为一谈
5. 场景题里不会同时看稳定性和空间限制

20. 8.7 重点展开

20.1 为什么外部排序和前面的排序问题已经不是一回事

前面的内部排序，默认都有一个很重要的前提：

1. 数据基本都能放进内存
2. 主要矛盾是比较次数和移动次数

但外部排序的前提变了：

1. 数据量太大
2. 内存放不下全部记录
3. 需要频繁从磁盘读入、写回

这时真正的主要矛盾就不再只是：

1. 比较次数多少

而变成：

1. 读写磁盘多少次
2. 要做多少趟归并
3. 每一趟能归并多少路

所以外部排序和内部排序最大的区别，不是“算法名字不同”，而是：

优化目标已经从 CPU 内部操作，转向 I/O 代价。

20.2 外部排序最该抓的主线：先生成初始归并段，再多路归并

外部排序最核心的流程可以先记成两步：

1. 先把大文件分批读入内存
2. 每批在内存里排好，形成若干初始归并段
3. 再对这些有序段反复做多路归并

所以外部排序真正的主体不是“原始数据直接一次排好”，而是：

1. 先局部排好
2. 再逐步归并成更大的有序段

如果学生把这条主线记住，后面的“归并趟数”“几路归并”“败者树”就都更容易挂上去。

20.3 为什么外部排序特别关心归并趟数

归并趟数之所以重要，是因为每多一趟归并，通常就意味着：

1. 整批数据又要读一遍
2. 再写一遍

也就是说，趟数每增加一次，I/O 成本都会明显增加。

所以外部排序的一个核心目标就是：

尽量减少归并趟数。

这也是为什么教材里会特别强调：

1. 多路归并
2. 初始归并段长度
3. 败者树

这些结构和技巧。

20.4 为什么会有多路归并，而不是一直二路归并

如果每次都只做二路归并，那么：

1. 归并层数会比较多
2. 趟数也可能增加

于是外部排序更希望：

1. 每次尽量同时归并更多路
2. 让归并层数降下来

这就是多路归并出现的直接原因。

更形象地说：

1. 二路归并像两条小河汇一条
2. 多路归并像多条小河一次汇成大河

如果一次能合更多路，整体趟数通常更少。

20.5 多路归并为什么又不能无限增大路数

这也是一个特别值得解释清楚的点。

虽然路数越多，理论上归并趟数可能越少，但它不是越大越好。

因为路数增大后：

1. 内存里要同时管理更多输入缓冲区
2. 每次选最小记录也会更复杂
3. 系统实现成本会上升

所以真正的设计思路不是“无限增大 k”，而是：

1. 在内存容量、缓冲区数量和归并效率之间找平衡

20.6 败者树为什么会出现

败者树看起来像一个很“偏工程”的结构，但它的目标非常单纯：

让多路归并时反复选最小元素这件事更高效。

因为多路归并时，每次都要做一件事：

1. 在若干路当前记录中找最小者
2. 输出它
3. 再从它所在那一路补进下一个记录

如果每次都从头比较一遍，代价会比较大。

于是败者树就相当于：

1. 提前把比较关系组织起来
2. 让下一次“选最小”变得更省事

学生这一节最该抓的不是实现细节，而是：

1. 败者树是为“多路归并中的反复选最小”服务的

20.7 为什么外部排序也和归并排序有天然联系

这一点很适合拿来帮助学生建立前后章节联系。

内部排序里的归并排序是：

1. 先分
2. 再把两个有序段归并

外部排序的主线则是：

1. 先形成若干个已经有序的归并段
2. 再把这些归并段继续归并

所以外部排序其实可以看成：

1. 归并思想在“大数据 + 外存”环境下的延伸

区别在于：

1. 内部排序更关心比较和递归
2. 外部排序更关心 I/O、缓冲区和归并趟数

20.8 8.7 高频题最常考什么

这一节高频题通常集中在下面几类：

1. 外部排序和内部排序的区别
2. 初始归并段的含义
3. 多路归并为什么能减少趟数
4. 归并趟数计算题
5. 败者树的作用
6. 缓冲区和路数的关系

所以做这类题时，先问自己：

1. 它在考“概念”
2. 还是在考“趟数计算”
3. 还是在考“结构作用”

20.9 8.7 当前最容易丢分的点

这一节当前最容易错的地方主要有：

1. 还在用内部排序的思维看外部排序
2. 只会背“多路归并减少趟数”，但说不清为什么
3. 不理解败者树是为谁服务的
4. 归并趟数题时不会把“初始归并段个数”和“每趟归并路数”对应起来
5. 以为路数越大一定越好

21. 第8章题型索引

21.1 基本概念与性质类

这一类题主要围绕：

1. 排序的定义
2. 稳定性
3. 内部排序与外部排序
4. 比较型排序与非比较型排序

这类题表面像概念题，实际上在考：

1. 你是否理解排序评价维度
2. 你是否会把某个排序算法放进正确类别

21.2 插入排序与交换排序类

这一类题主要包括：

1. 直接插入排序过程题
2. 折半插入排序优化点
3. 冒泡排序过程题
4. 冒泡排序提前结束
5. 快速排序划分过程题
6. 快速排序最坏情况分析

这类题最核心的是：

1. 看懂每一趟做了什么
2. 分清“插入”“交换”“划分”三种动作

21.3 选择排序与堆排序类

这一类题主要包括：

1. 简单选择排序每趟找最小值
2. 简单选择排序稳定性判断
3. 大根堆 / 小根堆性质
4. 建堆过程
5. 堆排序下滤过程
6. 堆排序与完全二叉树对应关系

这类题最该抓的是：

1. 选择排序在“找最值”
2. 堆排序在“结构化地找最值”

21.4 归并、计数、基数排序类

这一类题主要包括：

1. 归并排序递归过程
2. 归并操作过程
3. 归并排序稳定性和空间复杂度
4. 计数排序使用条件
5. 基数排序按位分配与收集
6. 为什么基数排序要求稳定

这类题最该抓的是：

1. 归并排序靠“合并有序段”
2. 计数、基数排序不完全依赖关键字比较

21.5 综合比较类

这一类题主要包括：

1. 时间复杂度比较
2. 空间复杂度比较
3. 稳定性比较
4. 场景选择题
5. “哪种排序更适合基本有序序列”之类的综合判断

这类题最该抓的是：

1. 不能脱离场景谈“最好”
2. 要同时看稳定性、空间和数据特点

21.6 外部排序类

这一类题主要包括：

1. 外部排序与内部排序的区别
2. 初始归并段
3. 多路归并
4. 归并趟数
5. 败者树作用

这类题最该抓的是：

1. 目标已经从比较次数转成 I/O 代价
2. 趟数和路数之间的关系

22. 刷题路径

22.1 基础训练：先把插入、冒泡、选择三类基础排序做稳

基础训练建议先刷：

1. 直接插入排序
2. 折半插入排序
3. 冒泡排序
4. 简单选择排序

目标是：

1. 先把“每一趟到底在做什么”真正弄清楚
2. 把稳定性和基本复杂度先建立起来

22.2 进阶训练：专刷快速排序和堆排序

进阶训练建议集中刷：

1. 快速排序划分题
2. 快速排序最坏情况题
3. 建堆题
4. 下滤题
5. 堆排序过程题

这一部分最重要的是：

1. 把 Partition 看懂
2. 把“数组下标 <-> 完全二叉树”看懂

22.3 强化训练：专刷归并、计数、基数排序

强化训练建议集中刷：

1. 归并过程题
2. 归并排序稳定性和空间复杂度
3. 计数排序适用条件题
4. 基数排序按位处理题
5. 比较型 / 非比较型排序区别题

这一部分的目标是：

1. 把“合并”和“分配 / 收集”这两种思维区分开

22.4 第四轮：专刷综合比较题

第四轮建议集中刷：

1. 时间复杂度比较
2. 空间复杂度比较
3. 稳定性比较
4. 场景选算法题

这一部分最重要的是：

1. 不再死记表格
2. 而是能根据场景做判断

22.5 第五轮：专刷外部排序

第五轮建议集中刷：

1. 初始归并段
2. 多路归并
3. 归并趟数
4. 败者树

这一部分的目标是：

1. 把外部排序和内部排序彻底区分开
2. 理解为什么排序目标已经变成减少 I/O

22.6 第六轮：整章综合回刷

最后一轮建议整章混着刷：

1. 先判断题目属于哪类
2. 再调动对应算法和比较维度

这一部分的目标不是“第一次学会”，而是：

1. 看见题就能迅速分类
2. 知道该从哪条主线切进去

23. 自学检查清单

23.1 概念层

学完第 8 章后，至少应该能不用看书直接说清：

1. 稳定性是什么意思
2. 内部排序和外部排序的区别
3. 比较型排序和非比较型排序的区别
4. 为什么排序算法不能脱离场景比较“绝对最好”

23.2 算法过程层

你至少应该能做到：

1. 手推直接插入排序每一趟
2. 手推冒泡排序每一趟
3. 手推快速排序一次划分
4. 手推简单选择排序每一趟
5. 手推建堆和一次下滤
6. 手推归并两个有序段

23.3 性质比较层

你至少应该能做到：

1. 分清哪些排序稳定、哪些不稳定
2. 分清哪些排序更适合基本有序序列
3. 分清哪些排序更依赖额外空间
4. 说清快速排序、堆排序、归并排序各自的优缺点

23.4 非比较型排序层

你至少应该能做到：

1. 说清计数排序适合什么条件
2. 说清基数排序为什么按位处理
3. 说清基数排序为什么通常要求稳定
4. 分清计数排序、基数排序和比较型排序的根本区别

23.5 外部排序层

你至少应该能做到：

1. 说清初始归并段是什么
2. 说清为什么要多路归并
3. 说清归并趟数为什么重要
4. 说清败者树是为谁服务的

23.6 代码层

你至少应该能做到：

1. 看懂 第8章普通代码版 中的插入、冒泡、选择、快速排序
2. 看懂 第8章普通代码版 中的 SiftDown 和 HeapSort
3. 看懂 第8章普通代码版 中的 Merge 和 MergeSort
4. 看懂 第8章普通代码版 中的 CountingSort
5. 卡住时能切到 第8章逐行注释版代码

23.7 阶段总结

到这里，第 8 章已经从“启动版”进入了“章节成品化中段”：

1. 主线讲义已经搭起来
2. 代码首稿已经完成
3. 逐行注释版已经补上
4. 题型索引、刷题路径、自学检查也已经补上

这意味着后面继续推进原书试题整理和详细解答时，已经有很稳的底座可用。

24. 原书试题区整理版

24.1 这一版整理的作用

这一部分不是把原书题目原样搬过来，而是把原书第 8 章试题按“考法”重新归类。

这样整理的价值主要有两点：

1. 学生做题前，能先判断题目属于哪一类，不会把整章排序题看成一团
2. 后面继续补逐题详细解答时，可以直接沿着这个分类往下展开

这一版目前先做三件事：

1. 把原书试题按知识块重新分组
2. 给出每类题在考什么
3. 给出对应的做题思路和易错点

24.2 基本概念与性质题

这一类题通常围绕：

1. 稳定性
2. 内部排序与外部排序
3. 比较型排序与非比较型排序
4. 时间复杂度、空间复杂度的基本判断

这类题表面上像“记忆题”，其实真正考的是：

1. 你是否理解每种排序的本质动作
2. 你能不能把某种性质和对应算法对上

做题思路：

1. 先判断题目问的是稳定性、复杂度还是分类
2. 再回到算法动作本身去解释
3. 不要只靠背表格

易错点：

1. 只记名字，不记动作
2. 把稳定性和“交换次数多少”混为一谈
3. 把外部排序也按内部排序思路来理解

24.3 插入排序与交换排序题

这一类题通常围绕：

1. 直接插入排序每一趟的过程
2. 折半插入排序优化了什么
3. 冒泡排序每一趟的结果
4. 冒泡排序提前结束条件
5. 快速排序划分过程
6. 快速排序最坏情况分析

这类题最常考的不是大定义，而是：

1. 每一趟到底做了什么
2. 某一步之后序列变成什么样
3. 为什么快排会好，也为什么会退化

做题思路：

1. 直接插入排序：盯“取出、后移、插回”
2. 冒泡排序：盯“相邻比较、逆序交换”
3. 快速排序：盯“枢轴划分”而不是只盯递归

易错点：

1. 把直接插入排序和冒泡排序都看成“换位置”
2. 把折半插入排序误解成整体复杂度也变成对数级
3. 快速排序没看懂 Partition 就开始强行背结论

24.4 选择排序与堆排序题

这一类题通常围绕：

1. 简单选择排序每一趟选最小值
2. 简单选择排序稳定性判断
3. 大根堆 / 小根堆性质
4. 建堆过程
5. 下滤过程
6. 堆排序每一趟结果

这类题最核心的考点有两条：

1. 选择排序是在“扫描未排序区找最值”
2. 堆排序是在“用堆结构化地找最值”

做题思路：

1. 选择排序题：每一趟先找最小位置，再看交换结果
2. 堆排序题：先判断当前是不是合法堆，再看是否需要下滤
3. 建堆题：从最后一个非叶结点开始向前调

易错点：

1. 误以为简单选择排序稳定
2. 不会把数组下标和完全二叉树位置对应起来
3. 堆排序时忘记堆的有效区间会逐步缩小

24.5 归并、计数、基数排序题

这一类题通常围绕：

1. 归并两个有序段
2. 归并排序递归过程
3. 归并排序稳定性和空间复杂度
4. 计数排序适用条件
5. 基数排序按位分配 / 收集
6. 为什么基数排序要求稳定

这类题的真正核心是：

1. 归并排序在做“合并有序段”
2. 计数排序和基数排序不再主要依赖关键字比较

做题思路：

1. 归并题：盯两个有序段的双指针合并
2. 计数排序题：先看值域是否合适
3. 基数排序题：先看按哪一位分配，再看收集顺序

易错点：

1. 把归并排序和快速排序都只记成“递归排序”
2. 以为计数排序适合所有整数排序
3. 记住了基数排序“按位排”，却不理解稳定性的作用

24.6 综合比较题

这一类题通常围绕：

1. 时间复杂度比较
2. 空间复杂度比较
3. 稳定性比较
4. 哪种算法更适合某种场景
5. 哪种算法适合基本有序、数据量大、稳定性要求高等条件

这类题最容易拉开差距，因为它在考：

1. 你是不是只会背单个算法
2. 还是已经能把整章放到一张比较图里

做题思路：

1. 先判断题目问的是“性质比较”还是“场景选算法”
2. 再锁定候选算法
3. 最后用稳定性、空间、复杂度和数据特点去排除

易错点：

1. 试图脱离场景谈“哪个排序最好”
2. 只会背复杂度，不会结合稳定性和空间限制

24.7 外部排序题

这一类题通常围绕：

1. 外部排序与内部排序的区别
2. 初始归并段
3. 多路归并
4. 归并趟数
5. 败者树作用

这类题最该抓的是：

1. 排序目标已经从比较次数转成 I/O 代价
2. 趟数、路数、缓冲区这些量之间有关系

做题思路：

1. 区分题目是在考概念还是在考归并趟数
2. 看清有多少初始归并段
3. 看清每趟是几路归并

易错点：

1. 不会把“初始归并段个数”和“归并路数”联系起来
2. 只会背“败者树更高效”，却说不清它在优化什么

24.8 这一版整理后的使用方法

现在最推荐这样用这部分：

1. 做题前先看题型分类，判断题目属于哪一类
2. 做题时按该类题的固定思路去推
3. 做完后再回看对应章节内容和代码

这样用会比“从头往后乱刷”更稳，因为它会强迫学生先建立题型识别能力。

25. 原书试题逐题详细解答版（基础部分）

25.1 高频题 1：为什么直接插入排序通常适合基本有序序列

题目本质：

这类题不是只问“哪个算法快”，而是在问：

当序列已经接近有序时，哪个算法的额外工作会明显减少。

正确结论：

1. 直接插入排序通常很适合基本有序序列

详细思路：

1. 直接插入排序每次把一个新元素插入前面已排序区
2. 如果序列本来就基本有序，那么大多数元素已经离正确位置不远
3. 这样从后往前找插入位置时，比较次数和后移次数都会减少
4. 所以它在这种场景下会表现得比完全乱序时更轻松

易错点：

1. 只会背“插入排序适合基本有序”，却说不出原因
2. 把“适合基本有序”和“整体复杂度已经变成最优”混为一谈

25.2 高频题 2：折半插入排序到底优化了什么

题目本质：

这类题在考你是不是分清了“比较”和“移动”这两类代价。

正确结论：

1. 折半插入排序主要优化的是查找插入位置时的比较过程
2. 它并没有从根本上消除元素移动

详细思路：

1. 直接插入排序中，有两部分工作：
2. 找插入位置
3. 后移元素腾位置
4. 折半插入排序只是把“找位置”改成了更快的折半定位
5. 但一旦位置确定，该后移的元素还是要后移
6. 所以不能简单把它理解成“整体代价突然变得特别低”

易错点：

1. 以为折半插入排序会让整个排序复杂度都变成对数级
2. 不会区分比较次数减少和移动次数不变

25.3 高频题 3：冒泡排序为什么加了标志位就能提前结束

题目本质：

这类题在考的是“排序过程中如何发现序列已经有序”。

正确结论：

1. 如果某一趟扫描下来一次交换都没有发生，说明序列已经有序
2. 后面的趟数可以直接省掉

详细思路：

1. 冒泡排序每次只在相邻逆序时交换
2. 如果一整趟都没有发生交换，说明所有相邻元素都已经满足局部有序
3. 相邻元素都已经有序时，整个序列也就已经有序
4. 所以后续不需要再继续做无意义的扫描

易错点：

1. 只记得有个 flag，但不知道它到底在判断什么
2. 误以为提前结束只是“代码优化小技巧”，看不到它背后的排序状态判断

25.4 高频题 4：快速排序为什么最该盯 Partition

题目本质：

这类题在考你是不是抓住了快速排序的灵魂动作。

正确结论：

1. 快速排序最核心的是划分
2. 枢轴一旦划分完成，其最终位置就确定了

详细思路：

1. 快速排序不是先递归才有意义，而是先通过划分把一个元素放到正确位置
2. 划分后，左边元素都不大于枢轴，右边元素都不小于枢轴
3. 这样左右两边就变成两个规模更小但同类的问题
4. 递归只是把这个动作在左右子区间继续重复

易错点：

1. 只盯“递归”两个字，没看懂划分
2. 以为快速排序每次都能平均分开，忽略最坏情况

25.5 高频题 5：为什么简单选择排序通常不稳定

题目本质：

这类题在考的是“稳定性到底由什么决定”。

正确结论：

1. 简单选择排序通常不稳定

详细思路：

1. 每一趟选择排序会在后面未排序区里找到最小元素
2. 然后把它直接交换到前面
3. 这个交换动作可能让两个关键字相同的元素前后顺序发生变化
4. 所以它不是稳定排序

更重要的是要形成一个判断习惯：

1. 稳定性不看“交换次数少不少”
2. 而看“相等元素的相对顺序会不会变”

易错点：

1. 认为“一趟只交换一次，所以稳定”
2. 把稳定性和交换次数多少混掉

25.6 高频题 6：堆排序建堆为什么从最后一个非叶结点开始

题目本质：

这类题在考的是你是否理解“哪些结点需要调整，哪些不需要”。

正确结论：

1. 建堆时从最后一个非叶结点开始向前调整

详细思路：

1. 叶结点本身没有孩子，所以天然满足堆的局部性质
2. 真正可能不满足堆性质的，是那些有孩子的结点
3. 最后一个非叶结点后面的全是叶子
4. 所以从最后一个非叶结点开始，向前逐个做下滤调整，就能逐步把整个序列整理成堆

易错点：

1. 以为建堆必须从根开始
2. 只记住公式，不知道为什么叶子结点不用调

25.7 高频题 7：归并排序为什么通常稳定

题目本质：

这类题在考的是“稳定性和归并过程之间的关系”。

正确结论：

1. 归并排序通常是稳定的
2. 前提是归并时相等元素优先取左边

详细思路：

1. 归并排序真正的关键是把两个有序段合并
2. 如果两个有序段当前元素相等，而代码选择先放左段元素
3. 那么原来左边出现的元素仍然会排在右边那个相等元素前面
4. 这样相等元素的相对次序就保住了

易错点：

1. 只会背“归并排序稳定”，却说不清为什么
2. 不知道稳定性和归并时相等元素的处理规则有关

25.8 高频题 8：计数排序为什么不适合值域特别大的情况

题目本质：

这类题在考的是“算法适用条件”。

正确结论：

1. 计数排序更适合关键字范围不大的整数序列
2. 值域过大时，空间代价可能非常不划算

详细思路：

1. 计数排序要开一个计数数组
2. 这个数组大小和关键字值域直接相关
3. 如果值域很大，但实际元素数量并不多
4. 就会出现“数组很大，但很多位置都空着”的情况
5. 这样空间利用率会很差

易错点：

1. 只看到计数排序很快，就觉得所有整数排序都该优先用它
2. 忽略了值域大小这个前提

25.9 高频题 9：为什么基数排序通常要求每一趟稳定

题目本质：

这类题在考的是“多趟排序之间的前后衔接关系”。

正确结论：

1. 基数排序通常要求每一趟按位排序稳定

详细思路：

1. 基数排序不是一趟完成，而是按位一趟一趟处理
2. 低位先建立起来的相对次序，后面高位排序时不能被随便打乱
3. 如果某一趟不稳定，前面已经形成的有序关系就可能被破坏
4. 那样最终结果就不可靠

易错点：

1. 只背“基数排序稳定”，却说不清为什么
2. 不能把“低位已经排出的相对关系”这件事说清楚

25.10 高频题 10：为什么说“哪种排序最好”通常是伪问题

题目本质：

这类题在考的是你是否已经从“背算法”进入“按场景选算法”。

正确结论：

1. 排序算法很少有脱离场景的绝对最好

详细思路：

1. 有的题强调基本有序
2. 有的题强调稳定性
3. 有的题强调内存限制
4. 有的题强调值域大小
5. 有的题强调最坏情况也要可控

不同条件下，最合适的排序算法会完全不同。

所以真正成熟的回答方式应该是：

1. 先看数据特征
2. 再看稳定性要求
3. 再看空间限制
4. 最后再选算法

易错点：

1. 总想背一个“万能最优排序”
2. 场景题里不同时考虑稳定性和空间条件

25.11 高频题 11：外部排序为什么特别在意归并趟数

题目本质：

这类题在考的是“外部排序优化目标已经变了”。

正确结论：

1. 外部排序特别关心归并趟数，因为每多一趟通常都意味着整批数据又要多读写一次

详细思路：

1. 外部排序的数据通常在磁盘上
2. 每一趟归并，往往都要把数据重新读入、再写出
3. 所以趟数越多，I/O 成本就越大
4. 这也是为什么要强调多路归并和败者树这类结构

易错点：

1. 还在用内部排序的比较次数思维看外部排序
2. 只会背“趟数越少越好”，但说不清为什么

25.12 基础题解学习提示

这一部分先覆盖的是第 8 章最核心、最能建立题感的一批题：

1. 插入排序适用场景
2. 折半插入排序优化边界
3. 冒泡排序提前结束
4. 快速排序的划分主线
5. 选择排序稳定性
6. 堆排序建堆
7. 归并排序稳定性
8. 计数排序适用条件
9. 基数排序稳定性
10. 外部排序归并趟数

这意味着第 8 章现在已经不只是有“题型目录”，而是开始有“逐题详解层”了。

25.13 高频题 12：快速排序过程题为什么一定要先把枢轴路径走完整

题目本质：

这类题在考的不是你会不会背代码，而是你能不能把一次划分过程真正手推出来。

正确结论：

1. 快速排序过程题最稳的做法，是先固定枢轴，再完整走完一次划分路径

详细思路：

1. 先确定当前枢轴是谁
2. 再看左右指针或左右扫描是怎么移动的
3. 每移动一步，都要明确当前在找什么：
4. 右边找比枢轴小的
5. 左边找比枢轴大的
6. 最后枢轴落到的位置，就是它的最终位置
7. 这个位置后面不再参与本层递归

所以过程题里最怕的不是不会递归，而是：

1. 枢轴还没放稳
2. 就急着看左右子区间

易错点：

1. 枢轴还没归位就提前递归
2. 划分完后又把枢轴位置继续算进同一层子问题
3. 只盯序列变化，不盯“枢轴位置已经确定”这件事

25.14 高频题 13：堆排序每一趟结果题怎么做最稳

题目本质：

这类题在考你是否把“堆顶取最大值”和“剩余部分重新成堆”这两步分清楚了。

正确结论：

1. 堆排序每一趟都先把堆顶换到末尾
2. 然后只对前面剩余部分重新做下滤

详细思路：

1. 先确认当前序列是不是大根堆
2. 把堆顶最大值和当前末尾交换
3. 交换后，末尾元素已经就位，不再参与后续建堆
4. 再对前面剩余区间从根开始做一次下滤
5. 这样才得到“下一趟开始前”的合法堆

所以这类题固定节奏是：

1. 看交换
2. 看有效区间缩小
3. 看下滤恢复

易错点：

1. 交换完堆顶和末尾后，忘记下滤
2. 继续把已经排好位置的末尾元素算进堆里
3. 只会看最终结果，不会写中间每一趟结果

25.15 高频题 14：归并两个有序段时为什么一定要双指针同步看

题目本质：

这类题在考的是归并操作本身，而不是整个递归框架。

正确结论：

1. 归并两个有序段时，要用两个指针分别指向两个有序段当前未处理的最前元素

详细思路：

1. 两个子段本身都已经有序
2. 所以每次只要比较两个子段当前最前面的元素
3. 较小者先放入结果数组
4. 对应指针后移
5. 一段耗尽后，把另一段剩余元素整体接上

这类题真正关键的不是“记住代码”，而是：

1. 明白为什么只比较当前两个最前元素就够了

易错点：

1. 归并时还想回头看已经处理过的元素
2. 一段结束后，忘记把另一段剩余部分整体接上
3. 把归并排序和快速排序的过程混掉

25.16 高频题 15：为什么归并排序通常时间复杂度更稳定

题目本质：

这类题在考你是否理解“归并排序的工作量为什么比较规律”。

正确结论：

1. 归并排序的时间复杂度通常比较稳定，因为它总是按比较固定的方式分解和合并问题

详细思路：

1. 不管原序列初始分布怎样
2. 归并排序都会持续把问题一分为二
3. 再把两个有序段合并回来
4. 这种“分 + 合”的结构比较稳定
5. 所以它不像快速排序那样特别依赖划分是否均匀

易错点：

1. 只会背结论，不会和快速排序对比着理解
2. 把“递归排序”都想成一样稳定

25.17 高频题 16：比较题里为什么不能把快速排序、堆排序、归并排序只按复杂度排队

题目本质：

这类题在考你是不是已经从“背表格”过渡到“看场景选算法”。

正确结论：

1. 快速排序、堆排序、归并排序不能只看时间复杂度，还要看稳定性、空间代价和最坏情况表现

详细思路：

1. 快速排序平均表现通常很好，但最坏情况会恶化
2. 堆排序性能较稳，但通常不稳定
3. 归并排序也较稳，而且通常稳定，但要额外辅助空间
4. 所以这三者没有脱离场景的绝对胜负

真正成熟的判断方式是：

1. 先看数据规模
2. 再看稳定性要求
3. 再看空间限制
4. 再看是否要控制最坏情况

易错点：

1. 只看到平均复杂度就断言谁最好
2. 忽略稳定性和额外空间
3. 不会把“最坏情况是否可控”纳入判断

25.18 高频题 17：为什么计数排序和基数排序经常放在一起考

题目本质：

这类题在考你是否真正建立了“非比较型排序”这个类别。

正确结论：

1. 计数排序和基数排序经常放在一起考，因为它们都不主要依赖关键字两两比较来确定次序

详细思路：

1. 计数排序通过统计出现次数来恢复有序序列
2. 基数排序通过按位分配和收集逐步建立有序性
3. 它们和插入、交换、选择、归并这类排序的思维方式明显不同
4. 所以教材和试题中常把它们作为“非比较型排序”来对照考察

易错点：

1. 只记住两个算法名字，不知道它们为什么经常一起出现
2. 不能说清它们和比较型排序的边界

25.19 高频题 18：外部排序为什么要同时考虑初始归并段和归并路数

题目本质：

这类题在考你是否真正理解归并趟数是怎么来的。

正确结论：

1. 外部排序的归并趟数，同时取决于初始归并段个数和每一趟归并的路数

详细思路：

1. 初始归并段越多，后面需要归并的对象越多
2. 每一趟归并路数越大，一次能合并掉的段就越多
3. 所以两者一起决定“还要做几轮归并”
4. 这也是为什么外部排序题里常常同时给出：
5. 初始归并段个数
6. 可做几路归并

易错点：

1. 只看路数，不看初始归并段个数
2. 只背“多路归并趟数少”，却不会把它用到具体题里

25.20 进阶题解学习提示

这一部分覆盖的是第 8 章里最容易拉开差距的过程题和综合比较题：

1. 快速排序划分过程
2. 堆排序每一趟结果
3. 归并过程
4. 归并排序与快速排序的稳定性 / 复杂度对照
5. 非比较型排序边界
6. 外部排序的归并趟数理解

学完这一部分后，第 8 章已经不只是“有题型目录”，而是开始具备比较完整的题解层了。

25.21 排序代码专题：基数排序与外部排序

这里把第 8 章之前最明显的两个代码缺口补齐了：

1. 基数排序真实代码
2. 外部排序流程模拟代码

这两块很关键，因为它们正好对应了“前面内部排序主线”和“后面外部排序主线”里最容易让学生回原 PDF 的地方。

25.21.1 基数排序的真实代码覆盖内容

代码中已经补入以下内容：

1. 第8章普通代码版 里的 GetMaxValue
2. 第8章普通代码版 里的 CountingSortByDigit
3. 第8章普通代码版 里的 RadixSortLSD

这三段代码连起来，正好把基数排序最该抓的主线落成了真实程序：

1. 先确定最高位需要处理到哪里
2. 再从个位开始
3. 每一趟都按当前位做一次稳定计数
4. 一位一位把整体有序性“搭起来”

这样学生以后再看到“为什么基数排序要求稳定”这类题，就不需要只背定义了。
直接对着 CountingSortByDigit 看就能明白：

1. 这一趟只按当前位分类
2. 如果同位元素的原相对顺序乱了
3. 前面已经建立好的低位有序性就会被破坏

当前程序运行时已经能直接看到：

1. Radix sort: 329 355 436 457 657 720 839

这意味着基数排序现在不只是“讲义里会说”，而是已经能真正跑出来。

25.21.2 外部排序的真实代码覆盖内容

外部排序这一部分不再停留在概念说明，而是配套给出一个“外部归并流程模拟版”的真实程序：

1. 第8章普通代码版 里的 PrintRuns
2. 第8章普通代码版 里的 MergePass
3. 第8章普通代码版 里的 ExternalMergeSortSimulation

这三段代码最重要的作用，不是模拟磁盘 I/O 的所有细节，而是把外部排序最核心的流程跑出来：

1. 先生成初始归并段
2. 再按段长一趟一趟归并
3. 每归并一轮，归并段会变大
4. 最后全部并成一个有序结果

这正好对应了教材里最常考的那条主线：

1. 初始归并段是什么
2. 归并路数和归并趟数怎么影响总流程
3. 为什么外部排序最在意“段”和“趟”

当前程序里已经能直接看到这些关键输出：

1. Initial runs
2. After merge pass 1
3. After merge pass 2
4. External merge sort simulation

也就是说，现在学生已经可以不靠原书图示，也能直接从程序输出看懂：

1. 初始归并段长什么样
2. 每一趟归并后段是怎么变大的
3. 为什么归并趟数会影响整体代价

25.21.3 代码层能力提升

学完这一部分以后，第 8 章代码层终于形成了更完整的闭环：

1. 比较型排序有真实代码
2. 非比较型排序不再只剩计数排序
3. 外部排序不再只有概念，没有程序支撑

这一步很关键，因为它直接减少了第 8 章中回原 PDF 查阅以下内容的需要：

1. 基数排序按位处理过程
2. 外部排序初始归并段
3. 多趟归并流程图

25.22 外部排序专题：败者树与置换-选择

在已经补足“外部排序主流程”的基础上，这里继续补入外部排序中最容易在题目里出现的两块内容：

1. 败者树
2. 置换-选择

25.22.1 败者树的真实代码覆盖内容

代码中已经补入以下内容：

1. 第8章普通代码版 里的 LoserTreeAdjust
2. 第8章普通代码版 里的 BuildLoserTree
3. 第8章普通代码版 里的 LoserTreeDemo

这三段代码最重要的意义，不是把败者树写成一个特别庞杂的工程组件，而是把它最该让学生理解的那条主线跑出来：

1. 多路归并时，并不是每次都把所有路重新完整比较一遍
2. 败者树把“上一轮输掉的比较关系”保留下来
3. 所以下一轮只需要沿一条路径调整

这正是教材和试题里那句“败者树能减少关键字比较”的真正落地点。
现在学生不需要只背这句话了，因为程序已经能直接输出：

1. Loser tree merge order: 5 7 9 12 18

也就是说，败者树现在已经不只是一个抽象名词，而是有了可观察的“选优过程”。

25.22.2 置换-选择的真实代码覆盖内容

置换-选择这块，代码中已经补入以下内容：

1. 第8章普通代码版 里的 ReplacementSelectionRuns

这段代码虽然是教学版实现，但已经把这类题最该掌握的核心机制跑出来了：

1. 内存区先装一批记录
2. 每次输出当前可输出的最小记录
3. 新读入的记录如果还能接在当前归并段后面，就继续留在本段
4. 如果已经接不上，就冻结到下一段

这一步非常重要，因为学生以前最容易只记结果：

1. 置换-选择能生成更长的初始归并段

但说不清“为什么更长”。
现在对着程序输出，就能更形象地理解：

1. 当前段并不是机械地固定长度
2. 它会尽量把还能继续保持非降序的记录都接进去
3. 真接不上的记录，才被推迟到下一段

当前程序已经能直接看到：

1. Replacement selection runs
2. Run 1
3. Run 2

这就把“为什么初始归并段会变长”从一句结论，变成了一个可观察的过程。

25.22.3 外部排序能力提升

学完这一部分以后，第 8 章外部排序已经形成了比以前完整得多的支撑链：

1. 有概念解释
2. 有流程模拟
3. 有归并段输出
4. 有败者树选优演示
5. 有置换-选择生成初始归并段的真实程序

这意味着学生现在再遇到：

1. “为什么要用败者树”
2. “置换-选择为什么能增加初始归并段长度”
3. “外部排序为什么不只是简单归并”

这几类题时，已经更不需要回原 PDF 查原图和原过程了。

站内代码入口

• 对应代码专题：第8章 排序代码
• 如果你想逐行对照实现，建议把正文页和代码专题页一起打开。

继续阅读

← 上一章：第7章 查找