本讲定位：四级客观题分值最集中的一讲。官方大纲把「排序算法」这一个知识块拆成了三项内容（三种排序 + 复杂度/稳定性 + 复杂度估算），2026 年 3 月真题判断题第 9 题直接考”选择排序和插入排序能否互相替代”。这一讲的东西几乎每场必考，而且是纯送分题——只要背熟、练熟。
对应官方大纲：四级知识块 6「排序算法」——冒泡排序、插入排序、选择排序；时间复杂度、空间复杂度、算法稳定性；简单算法复杂度的估算（含多项式、指数复杂度）。另涉及内排序与外排序的概念。
前置知识：一维数组、循环嵌套、第 03 讲（结构体排序）。
代码说明：本讲所有代码及每一趟的中间结果均已用 g++ 11.5 编译运行逐趟打印验证，文中表格即程序实际输出。
| 内排序 | 外排序 | |
|---|---|---|
| 定义 | 待排数据全部装进内存 | 数据量太大，内存装不下，需借助外存（硬盘）分批处理 |
| 典型场景 | 排 10 万个数 | 排 100GB 的日志文件 |
| 本讲三种排序 | ✅ 都是内排序 | — |
考点：选择题问”下列哪个是外排序”或”冒泡排序属于内排序还是外排序”。记住：四级学的三种全是内排序。
定义：排序后，值相等的元素之间的相对先后顺序保持不变，就叫稳定（stable）。
看一个具体例子。设有三个元素，其中两个 5 分别标记为 $5_a$ 和 $5_b$（$5_a$ 原本在前）：
排序前： [ 5ₐ , 5_b , 3 ]
稳定的排序结果： [ 3 , 5ₐ , 5_b ] ← 5ₐ 仍在 5_b 前面 ✅
不稳定的排序结果： [ 3 , 5_b , 5ₐ ] ← 顺序被换了 ❌
注意：两个结果的数值序列完全一样（3 5 5），“稳定”说的不是排序对不对，而是相等元素的原始顺序有没有被打乱。
学生常问”稳定不稳定有什么关系，反正都排好了”。用这个例子回答：
有一份成绩表，已经按姓名字典序排好了。现在要按分数从高到低重排，要求分数相同的人仍然按姓名字典序排列。
如果第二次排序是稳定的，直接排一遍就完事了——因为分数相同的人会保持上一次（按姓名）的顺序。
如果不稳定，就得写复杂的双关键字比较函数。
$$ \boxed{\text{稳定排序的价值：可以通过“先排次关键字，再排主关键字”实现多关键字排序}} $$
教学提示：这个例子一定要讲，否则学生只会死记”冒泡稳定、选择不稳定”，遇到变式题就懵。