第二十六讲：内部排序比较与外部排序
排序这个话题，咱们前面花了不少篇幅。从冒泡到快排，从堆排到归并，各种内部排序算法都过了一遍。今天我想换个角度，把这些算法放在一起做个横向对比。然后咱们再聊聊外部排序——当数据量大到内存装不下时，该怎么玩。
一、内部排序算法的横向对比
先说说我个人的习惯。我在项目中选排序算法时，一般会问自己三个问题：数据量多大？数据本身有什么特征？对稳定性的要求高不高？
下面这张表，是我这些年总结出来的经验值，你可以直接拿来参考。
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 | 小规模数据，教学演示 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 | 小规模数据，交换次数少 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 | 基本有序的小数据，效率极高 |
| 希尔排序 | O(n^1.3~1.5) | O(n²) | O(1) | 不稳定 | 中等规模数据，工程中常用 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 | 大规模数据，默认首选 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 需要稳定排序的大数据 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 | 内存紧张的大数据 |
| 计数排序 | O(n+k) | O(n+k) | O(k) | 稳定 | 数据范围小，整数排序 |
| 基数排序 | O(d(n+k)) | O(d(n+k)) | O(n+k) | 稳定 | 多关键字排序，字符串 |
核心结论：没有银弹。快速排序在大多数情况下表现最好，但如果你需要稳定性，归并排序是更好的选择。如果内存非常有限，堆排序的空间优势就体现出来了。
二、如何选择排序算法？
说实话，这个问题没有标准答案。但我可以分享一些实战经验。
2.1 看数据规模
- n < 50：插入排序就够了。别小看它，在小数据量下，插入排序的常数因子非常小，甚至比快排还快。
- 50 < n < 10000：希尔排序是个不错的选择。我曾在嵌入式项目中用过它，效果很好。
- n > 10000：快排、归并、堆排三选一。我个人偏爱快排，但要注意避免最坏情况。
2.2 看数据特征
- 基本有序：插入排序的时间复杂度可以降到O(n)。快排反而会退化到O(n²)。
- 大量重复元素：三路快排比普通快排好得多。
- 数据范围很小：计数排序是王者，O(n)搞定。
2.3 看稳定性要求
我曾经在一个金融项目中，需要对交易记录先按时间排序，再按金额排序。这时候就必须用稳定排序。归并排序是首选，基数排序也行。
避坑指南：我曾经在项目中直接用快排处理一个已经有序的数组，结果递归深度达到n，栈溢出了。后来我改用随机选取pivot，问题就解决了。你想想看，一个简单的随机化，就能避免最坏情况，何乐而不为？
三、外部排序的基本概念
好了，内部排序聊完了。现在咱们进入正题——外部排序。
什么是外部排序？说白了，就是数据量大到内存装不下，必须借助磁盘来完成的排序。比如你要排序一个100GB的文件，而你的内存只有8GB，这时候内部排序就无能为力了。
3.1 外部排序的核心思想
外部排序的基本策略是分而治之：
- 分割：将大文件分成若干个小块，每块都能装入内存。
- 内部排序：对每个小块进行内部排序，生成有序的"归并段"。
- 归并：将多个有序的归并段合并成一个完整的有序文件。
嗯，这里要注意：外部排序的时间开销主要来自磁盘I/O。内存中的排序再快，也快不过磁盘读写的瓶颈。所以外部排序优化的核心，就是减少磁盘读写次数。
3.2 两路归并 vs 多路归并
最简单的归并方式是两路归并——每次合并两个归并段。但这样需要多次扫描磁盘。举个例子：
- 如果有8个归并段，两路归并需要3趟（8→4→2→1）。
- 如果使用4路归并，只需要2趟（8→2→1）。
你看，路数越多，趟数越少，磁盘I/O就越少。但路数多了，内存中同时比较的元素也多了，这又带来了新的问题。
四、多路归并排序与败者树
多路归并的核心难点在于：如何在k个有序序列中，快速找到最小值？
最直接的方法是每次比较k个元素，找出最小的那个。但这样每输出一个元素，就要比较k-1次。如果总共有n个元素，时间复杂度就是O(nk)。当k很大时，这个开销就不可接受了。
4.1 败者树登场
败者树是解决这个问题的经典数据结构。它的思路是：用一棵完全二叉树来记录比较过程中的"败者"，从而快速找到"胜者"。
我画了一张图，帮你理解败者树的结构和工作流程。
4.2 败者树的工作原理
败者树的调整过程很有意思。每次输出胜者后，从对应的归并段取一个新元素，然后从叶子节点向上调整。调整时，只需要和父节点比较，败者留在父节点，胜者继续向上。
这样，每输出一个元素，只需要进行log₂k次比较。相比之前的O(k)比较，效率提升了一个档次。
关键点：败者树的名字来源于它记录的是"败者"而不是"胜者"。这个设计的好处是，当胜者被输出后，新元素只需要和父节点（即之前的败者）比较，就能快速找到新的胜者。说白了，就是利用历史信息来加速比较。
4.3 代码实现要点
下面是一个败者树的核心代码框架，我简化了一些细节，但保留了关键逻辑。
#define K 4 // 归并路数
// 败者树节点
int loser[K]; // 记录败者的索引
int leaf[K + 1]; // 叶子节点，leaf[K]存放最小值
// 调整函数：从叶子节点leaf[s]开始向上调整
void adjust(int s) {
int t = (s + K) / 2; // 父节点在loser数组中的位置
while (t > 0) {
if (leaf[s] > leaf[loser[t]]) {
// 当前节点比父节点记录的败者大，交换
int temp = s;
s = loser[t];
loser[t] = temp;
}
t /= 2;
}
loser[0] = s; // 最终胜者
}
// 初始化败者树
void initLoserTree() {
// 将所有叶子节点初始化为最小值
leaf[K] = -INF;
for (int i = 0; i < K; i++) {
loser[i] = K; // 初始败者指向最小值节点
}
// 从每个叶子节点开始调整
for (int i = K - 1; i >= 0; i--) {
adjust(i);
}
}
// 多路归并主流程
void mergeSort() {
initLoserTree();
while (leaf[loser[0]] != MAX_VAL) {
int winner = loser[0];
output(leaf[winner]); // 输出胜者
leaf[winner] = next(winner); // 从对应归并段取下一个元素
adjust(winner); // 重新调整
}
}注意：上面的代码是教学简化版。实际工程中，你需要处理归并段耗尽的情况。我一般会在每个归并段末尾放一个哨兵值（比如INT_MAX），这样当所有归并段都耗尽时，胜者自然就是哨兵，循环结束。
五、外部排序的性能分析
外部排序的时间开销主要由两部分组成：
- 内部排序阶段：对每个归并段进行排序，时间复杂度为O(m × n/m × log(n/m))，其中m是归并段数量。
- 归并阶段：需要logₖm趟归并，每趟需要读写全部数据。
磁盘I/O次数 = 2 × (1 + logₖm)。这个公式很关键，它告诉我们：增加归并路数k，可以减少归并趟数，从而减少磁盘读写。
但k不能无限增大。因为败者树需要占用内存，而且每个归并段需要分配一个输入缓冲区。内存是有限的，所以需要在k和缓冲区大小之间做权衡。
实战经验：我曾经在一个数据仓库项目中，需要排序100GB的日志文件。当时内存只有16GB，我选择了16路归并，每个缓冲区分配1GB。败者树只占用了很小的内存（16个节点），但归并效率比4路归并提升了将近一倍。
六、总结
内部排序和外部排序，本质上都是排序，但面对的约束条件完全不同。内部排序追求的是CPU效率，外部排序追求的是I/O效率。
选内部排序算法时，记住三点：数据量、数据特征、稳定性要求。选外部排序策略时，核心是减少磁盘读写次数，多路归并配合败者树是经典方案。
嗯，排序这个话题到这里就告一段落了。希望这些内容对你有帮助。
公众号:蓝海资料掘金营，微信deep3321