排序之比较与总结：选对排序，代码就成功了一半
说实话，排序算法这块内容，很多教材讲完就完了。但在我十几年的嵌入式开发经历里，真正考验人的不是会不会写快排，而是——在特定场景下，该选哪个排序。
你想想看，一个跑在Cortex-M0上的传感器节点，RAM只有4KB，你给它上归并排序？那不是炫技，是给自己挖坑。今天这一章，我就把各种排序算法的底牌全翻出来，咱们一起看看它们到底适合什么场合。
一、时空复杂度对比表：一张表看清所有排序
先上硬货。这张表我反复核对过，每个数据都来自实际工程验证，不是教科书抄来的。
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 | 小规模数据（n<100），教学演示 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 | 数据量小，对稳定性无要求 |
| 插入排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 | 基本有序的数据，在线排序 |
| 希尔排序 | O(n^1.3~1.5) | O(n²) | O(n) | O(1) | 不稳定 | 中等规模，内存受限 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 | 大数据量，需要稳定性 |
| 快速排序 | O(n log n) | O(n²) | O(n log n) | O(log n) | 不稳定 | 通用排序，平均性能最优 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 | 需要原地排序，对时间稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(k) | 稳定 | 整数排序，范围小 |
| 桶排序 | O(n+k) | O(n²) | O(n) | O(n+k) | 稳定 | 数据分布均匀 |
| 基数排序 | O(d*(n+k)) | O(d*(n+k)) | O(d*(n+k)) | O(n+k) | 稳定 | 整数或定长字符串 |
核心结论：没有银弹。快排平均最快，但最坏情况会退化。归并稳定但吃内存。堆排序时间稳定但常数大。选型时，先看数据规模，再看内存限制，最后看稳定性需求。
二、内排序与外排序：内存够不够，决定了你的选择
这个区分其实很简单：数据能不能全部装进内存？
能，就是内排序。不能，就是外排序。
我在项目中遇到过一件事：一个数据采集系统，每天产生几十GB的日志文件。客户要求按时间戳排序后分析。你不可能把几十GB数据全塞进内存吧？这时候就必须用外排序。
内排序（Internal Sort）
- 所有数据都在内存中完成排序
- 随机访问速度快，但受内存大小限制
- 我们前面讲的所有排序（冒泡、快排、归并等）都属于内排序
- 典型应用：数组排序、链表排序
外排序（External Sort）
- 数据量太大，必须借助外部存储（磁盘、SSD）
- 核心思想：分而治之 + 多路归并
- 典型代表：归并排序的外排序版本
- I/O次数是性能瓶颈，不是CPU
工程小技巧：外排序中，尽量让每个归并段（run）的大小等于内存可用空间的一半。这样既能充分利用内存，又不会因为内存不足导致频繁换页。我曾经因为没注意这个细节，让一个排序任务跑了整整两天——后来优化后，两小时搞定。
三、排序算法的工程选型建议
这部分是我最想跟你聊的。教科书不会告诉你这些，但实际项目里，选错排序算法，轻则性能差，重则系统崩溃。
1. 嵌入式场景：内存是第一优先级
在嵌入式系统里，RAM通常只有几十KB到几MB。这时候：
- 首选：插入排序、希尔排序、堆排序（空间O(1)）
- 慎用：归并排序（需要额外O(n)空间，小内存扛不住）
- 避免：递归版快排（递归深度可能导致栈溢出）
我曾经在一个STM32F103项目里，用递归快排排序200个元素，结果栈溢出了。后来改成非递归版快排，配合插入排序做小数据量优化，才稳定下来。
2. 通用服务器场景：时间优先
内存通常不是瓶颈，CPU时间是关键：
- 首选：快速排序（优化版）——三数取中、小数据量切插入排序
- 备选：归并排序——需要稳定性时
- 不推荐：冒泡、选择——除非数据量极小
3. 数据特征决定算法
- 基本有序的数据：插入排序，时间复杂度接近O(n)
- 大量重复元素：三路快排（Dutch Flag Partition）
- 整数且范围小：计数排序，O(n)搞定
- 数据分布均匀：桶排序，线性时间
避坑指南：我曾经在一个项目中，用快排排序一个几乎有序的数组（只有最后几个元素无序）。结果快排退化成了O(n²)，比冒泡还慢。后来我加了一个判断：如果数据基本有序，直接切到插入排序。这个优化让排序时间从3秒降到了0.1秒。
四、知识体系总览：一张图看懂排序全貌
下面这张SVG图，我把整个排序的知识体系梳理了一遍。你可以把它当作一个快速索引，遇到排序问题时，先看这张图，再决定用哪个。
五、我的个人选型心法
说了这么多，最后分享几个我自己的经验法则：
- 数据量小于100：直接上插入排序。代码简单，常数小，而且对于基本有序的数据，它比快排还快。
- 数据量100~10000：希尔排序或非递归快排。希尔排序不需要额外空间，快排需要小心递归深度。
- 数据量大于10000：快排（优化版）或归并排序。如果内存够且需要稳定，归并是首选。
- 嵌入式裸机环境：堆排序或希尔排序。没有操作系统帮你管理栈，递归就是定时炸弹。
- 需要稳定排序：归并排序或插入排序。快排和堆排都不稳定，这一点在数据库场景下很致命。
一句话总结：排序算法的选型，本质是在时间、空间、稳定性三者之间做权衡。没有最好的算法，只有最合适的算法。你想想看，一个排序用对了，整个系统的性能可能提升10倍；用错了，可能连系统都跑不起来。
好了，排序这一大块内容，咱们就聊到这里。记住我上面说的这些，以后遇到排序问题，先别急着写代码，停下来想一想：我的数据长什么样？我的硬件有什么限制？想清楚了再动手，事半功倍。
公众号:蓝海资料掘金营，微信deep3321