排序算法系列 12：选型指南——到底该用哪个？
前面 11 篇把十种排序算法一个个拆完了。最后这篇不讲新算法，聊一个更实际的问题：写代码的时候，排序该怎么选？
说白了，没有最好的排序算法，只有最适合当前场景的。
先把家底盘一遍
| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定 | 一句话特征 |
|---|---|---|---|---|---|
| 冒泡 | O(n²) | O(n²) | O(1) | ✓ | 相邻交换 |
| 选择 | O(n²) | O(n²) | O(1) | ✗ | 每轮选最小 |
| 插入 | O(n²) | O(n²) | O(1) | ✓ | 打扑克牌 |
| 希尔 | 好于 O(n²) | 看步长 | O(1) | ✗ | 分组插入 |
| 归并 | O(n log n) | O(n log n) | O(n) | ✓ | 拆分合并 |
| 快排 | O(n log n) | O(n²) | O(log n) | ✗ | 基准分区 |
| 堆排 | O(n log n) | O(n log n) | O(1) | ✗ | 堆顶最大 |
| 计数 | O(n + k) | O(n + k) | O(k) | ✓ | 统计次数 |
| 桶排 | ≈O(n) | O(n²) | O(n + k) | 看桶内 | 范围分桶 |
| 基数 | O(d × n) | O(d × n) | O(n + k) | ✓ | 按位排序 |
表格看着多，但选型的时候你只需要问自己几个问题。
决策路径
问题 1：数据量多大？
几十个以内 → 直接用插入排序。简单、快、常数开销小。很多高级排序算法在子数组小于一定阈值时都会退化到插入排序。
几百到几万 → 标准的比较排序（快排、归并）。
几十万以上 → 如果数据有特殊性质（整数、范围小、分布均匀），优先考虑非比较排序。否则还是快排/归并。
问题 2：需要稳定吗？
需要稳定 → 归并排序是最靠谱的通用选择。如果是小范围整数，计数排序稳定版也行。
不需要稳定 → 快排通常是默认选择。
什么时候需要稳定？典型场景是多字段排序：先按 A 字段排，再按 B 字段排。如果第二次排序是稳定的，B 相同的元素还能保持 A 的顺序。
问题 3：内存紧张吗？
紧张 → 堆排序。O(1) 额外空间，时间还是 O(n log n)。代价是实际速度略慢、不稳定。
不紧张 → 归并排序用 O(n) 额外空间换来稳定性和稳定的时间上界。
问题 4：数据是整数吗？范围大不大？
整数 + 范围小（比如 0~100 的分数） → 计数排序，O(n + k) 线性时间。
整数 + 分布均匀 → 桶排序。
多位整数或定长编码 → 基数排序。
问题 5：数据基本有序吗？
基本有序 → 插入排序接近 O(n)。冒泡排序加 swapped 优化也行，但插入排序更优雅。
实际工程里的排序长什么样？
你可能好奇：JavaScript 的 Array.sort()、Python 的 sorted()、Java 的 Arrays.sort() 底层用的到底是什么？
答案是：混合排序。没有哪个生产级排序实现只用单一算法。
几个例子：
- V8（JavaScript）：TimSort——归并排序 + 插入排序的混合体。数据块小于 64 时用插入排序，大块之间用归并合并。
- Python：也是 TimSort。
- C++ STL：Introsort——快排为主干，递归深度超过阈值切堆排，子数组小时切插入排序。
- Java：基本类型用双轴快排（Dual-Pivot QuickSort），对象用 TimSort。
这些实现的共同思路：用快排/归并处理大块数据，用插入排序收拾小块，用堆排兜底极端情况。
面试怎么答？
如果面试官问"你怎么选排序算法"，可以这么组织回答：
- 先分两大类：比较排序 vs 非比较排序
- 比较排序里，通用场景首选快排（性能好、空间小），要求稳定选归并，内存极度紧张选堆排
- 非比较排序在特定条件下更快：整数范围小用计数，分布均匀用桶排，多位数字用基数
- 小数据量或基本有序的数据，插入排序性价比最高
- 实际工程都是混合策略
别只背复杂度表，能说出"为什么选这个"比"它的复杂度是多少"更有分量。
整个系列回顾
冒泡 → 相邻交换，每轮最大的冒到后面
选择 → 每轮选最小值放前面
插入 → 像打扑克，新牌插到合适位置
希尔 → 大步分组插入，逐步缩小间距
归并 → 拆到最小再合并，合并时排序
快排 → 选基准分左右，递归处理
堆排 → 建堆取顶，堆顶是最大值
计数 → 统计出现次数，按顺序还原
桶排 → 按范围分桶，桶内各排各的
基数 → 逐位排序，低位到高位
这十种算法覆盖了排序领域最核心的思想：交换、选择、插入、分治、堆结构、空间换时间、分布映射、逐位处理。
学排序不是目的。通过排序理解这些算法设计思想，才是真正的收获。后面遇到更复杂的算法问题时，你会发现这些套路反复出现——到那时候你就知道，这系列的时间没白花。
系列导航