第十八章：排序高级——各种排序算法的比较与选择、外部排序、排序算法的稳定性分析
排序这个话题，咱们前面聊了不少。从冒泡到快排，从堆排到归并，每种算法都有它的脾气。今天这一章，我想把这些零散的知识点串起来，做个了断。
说白了，排序算法的选择，就像选工具。你不可能用一把扳手去拧所有螺丝。我当年刚入行时，就犯过这种错——在一个嵌入式项目里，数据量不大，但我硬上了快速排序，结果递归深度把栈给撑爆了。嗯，从那以后，我选排序算法就谨慎多了。
18.1 排序算法的稳定性分析
先聊一个容易被忽略的概念：稳定性。
什么叫稳定排序？简单说，就是两个相等的元素，排序后它们的相对位置不变。你想想看，如果排序对象是整数，稳定性好像没啥用。但如果是结构体，比如按成绩排序学生，成绩相同的学生，我们希望保持原来的学号顺序，这时候稳定性就派上用场了。
稳定排序算法： 冒泡排序、插入排序、归并排序、计数排序、基数排序
不稳定排序算法： 选择排序、快速排序、堆排序、希尔排序
我曾在项目中遇到过这样一个场景：需要先按班级排序，再按成绩排序。如果第二轮排序用的是稳定算法，第一轮的结果就能保留下来。当时我用了归并排序，完美解决。如果用了快排，那就得自己额外处理相同成绩的顺序了，麻烦得很。
小技巧： 如果你需要稳定排序，但手头只有不稳定算法，可以给每个元素加一个“原始索引”作为第二关键字。这样，不稳定算法也能变得“稳定”。
18.2 各种排序算法的比较
咱们来张表，把常见排序算法的时间、空间、稳定性都列清楚。这张表我建议你存下来，面试和写代码时都能用上。
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | 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) | 稳定 |
看到这张表，你可能会问：这么多算法，到底用哪个？
我个人习惯这样选：
- 数据量小（n < 1000）： 插入排序就够了。代码简单，没有额外空间，而且对近乎有序的数据表现极好。
- 数据量大，不要求稳定： 快速排序。平均性能最好，但要注意递归深度。我建议用三数取中法选pivot，避免最坏情况。
- 数据量大，要求稳定： 归并排序。虽然需要额外O(n)空间，但性能稳定，没有快排那种“抽风”的情况。
- 数据范围小，比如年龄、成绩： 计数排序或基数排序。O(n)的时间复杂度，比任何比较排序都快。
- 嵌入式环境，内存紧张： 堆排序。空间复杂度O(1)，而且最坏情况也是O(n log n)。
注意： 快速排序在数据量很大时，递归深度可能达到O(n)。我曾经在一个嵌入式项目中，递归深度超过了栈空间，导致程序崩溃。后来我改用了非递归版本的快排，或者直接上堆排序，才解决问题。
18.3 外部排序
前面聊的排序，都假设数据能一次性装入内存。但现实世界没这么美好。你想想看，如果要对一个10TB的日志文件排序，内存只有16GB，怎么办？
这时候就需要外部排序了。外部排序的核心思想就四个字：分而治之。
具体做法分两步：
- 分割阶段： 把大文件分成若干个小块，每块都能装入内存。对每块用内部排序（比如快排）排好，写回磁盘。这些排好序的小块叫“归并段”。
- 归并阶段： 用多路归并的方式，把这些归并段合并成一个完整的有序文件。
举个例子，假设内存只能装100条记录，但文件有1000条。我们先把文件分成10个块，每块100条。分别排序后，得到10个有序的归并段。然后，用10路归并，每次从每个归并段中取最小的记录，输出到结果文件。
这里有个关键点：多路归并。如果归并路数太少，归并的趟数就多，磁盘I/O次数就多。而外部排序的瓶颈恰恰是磁盘I/O，不是CPU计算。所以，我们通常用“败者树”或“堆”来优化多路归并，减少比较次数。
外部排序的核心公式：
总I/O次数 = 2 × 数据量 × (1 + logkM)
其中k是归并路数，M是归并段数量。路数越大，I/O次数越少。
我曾经参与过一个日志分析系统的开发，每天要处理上百GB的访问日志。我们用了外部排序，归并路数设为64路，配合败者树，把排序时间从原来的6小时压缩到了40分钟。嗯，优化I/O的效果就是这么明显。
18.4 排序算法的选择策略
说了这么多，到底怎么选？我总结了一个决策流程，画成图给你看。
这个流程图，是我多年经验的总结。你照着走，基本不会出错。
18.5 实战中的避坑指南
最后，分享几个我踩过的坑，希望能帮你少走弯路。
我曾经... 在一个实时系统中用了快速排序。数据量不大，但每次排序的时间波动很大。后来发现，快排在处理近乎有序的数据时，退化成O(n²)，导致系统响应超时。解决方案：改用归并排序，或者对快排做随机化处理。
我曾经... 在外部排序时，归并路数设得太大，结果内存被败者树占满了。记住：败者树需要k个节点，每个节点存一个记录。如果k太大，内存吃不消。一般建议k取16~128之间，具体看你的内存大小。
还有一个细节：排序算法的稳定性，在C语言的标准库中并没有保证。qsort()函数是不稳定的。如果你需要稳定排序，要么自己实现归并排序，要么用qsort()时给元素加上索引字段。
好了，排序这块的内容，咱们就聊到这儿。记住一句话：没有最好的排序算法，只有最合适的。根据你的数据量、内存、稳定性需求，选对工具，才能事半功倍。
公众号：蓝海资料掘金营，微信 deep3321