Appearance
排序算法对比
场景引入
学完各种排序算法后，最常见的困惑是：这么多排序算法，到底该用哪个？ 面试中也经常被问到"请比较几种排序算法的优缺点"或"在什么场景下用什么排序"。
本文将所有主流排序算法放在一起做全面对比，帮你建立系统化的认识。
十大排序算法总览
比较类排序
比较类排序通过元素之间的比较来决定顺序，理论下界为 O(n log n)。
| 算法 | 最好时间 | 平均时间 | 最坏时间 | 空间 | 稳定性 | 原地 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | 是 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 | 是 |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | 是 |
| 希尔排序 | O(n log n) | O(n^1.3)* | O(n²) | O(1) | 不稳定 | 是 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 | 否 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 不稳定 | 是 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 | 是 |
*希尔排序的复杂度取决于增量序列的选择，O(n^1.3) 是 Knuth 增量序列的经验值。
非比较类排序
非比较类排序利用数据的特殊性质，可以突破 O(n log n) 的下界。
| 算法 | 最好时间 | 平均时间 | 最坏时间 | 空间 | 稳定性 | 适用条件 |
|---|---|---|---|---|---|---|
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | O(k) | 稳定 | 整数，值域 k 不大 |
| 基数排序 | O(n × d) | O(n × d) | O(n × d) | O(n + k) | 稳定 | 整数/字符串，d 为位数 |
| 桶排序 | O(n + k) | O(n + k) | O(n²) | O(n + k) | 稳定 | 数据均匀分布 |
排序算法选择决策图
如何选择排序算法？
按数据规模
| 数据规模 | 推荐算法 | 原因 |
|---|---|---|
| n < 50 | 插入排序 | 常数因子小，代码简单 |
| 50 < n < 1000 | 快速排序/归并排序 | O(n log n) 开始体现优势 |
| n > 1000 | 快速排序（通用）/ 归并排序（需稳定） | 性能最优 |
| n 极大，内存不足 | 外部归并排序 | 唯一支持外部排序的方案 |
按数据特征
| 数据特征 | 推荐算法 | 原因 |
|---|---|---|
| 基本有序 | 插入排序 | 最好 O(n)，移动次数少 |
| 完全随机 | 快速排序 | 平均性能最优 |
| 大量重复元素 | 三路快排 | 相等元素不再参与递归 |
| 需要稳定排序 | 归并排序 | 唯一稳定的 O(n log n) 比较排序 |
| 值域小的整数 | 计数排序 | O(n + k)，突破比较排序下界 |
| 需要原地 + 最坏 O(n log n) | 堆排序 | 唯一满足这两个条件的算法 |
| 链表排序 | 归并排序 | 不需要随机访问，空间可优化为 O(1) |
按需求优先级
追求平均性能 → 快速排序（随机化基准）
追求最坏保证 → 堆排序或归并排序
追求稳定性 → 归并排序
追求空间最省 → 堆排序（O(1) 额外空间）
数据流式到达 → 插入排序（在线算法）
JavaScript 的 Array.sort() 用什么算法？
JavaScript 的 Array.sort() 在不同引擎中实现不同：
V8 引擎（Chrome / Node.js）
V8 在 2019 年将排序算法从快速排序切换为 TimSort。TimSort 是一种混合排序算法，由 Tim Peters 于 2002 年为 Python 设计，核心思路是：
- 发现自然有序片段（Run）：扫描数组，找到已经有序的连续子序列
- 短 Run 用插入排序扩展：如果 Run 太短（< minrun，通常 32-64），用插入排序补齐
- 合并 Run：用改进的归并排序将各个 Run 合并，合并策略确保栈上 Run 的长度满足特定不变式
TimSort 的优势：
- 最好情况 O(n)：已有序数据只需一次扫描
- 最坏情况 O(n log n)：不会退化
- 稳定排序：保持相等元素的相对顺序
- 对现实数据高效：现实中的数据往往具有局部有序性，TimSort 能利用这一特点
SpiderMonkey（Firefox）
同样使用归并排序的变种。
重要提示
Array.sort() 默认按字符串字典序排序！排数字必须传比较函数：
javascript
// 错误：[1, 10, 2, 20, 3] → [1, 10, 2, 20, 3]（字典序）
[3, 1, 20, 10, 2].sort()
// 正确：[1, 2, 3, 10, 20]
[3, 1, 20, 10, 2].sort((a, b) => a - b)面试中最常考的排序算法
根据频率排序：
第一梯队（必须手写）
- 快速排序 — 手写 partition，理解随机化和三路分区
- 归并排序 — 手写 merge，理解分治递归，会求逆序对
- 堆排序 — 手写 heapify，理解建堆过程
第二梯队（理解原理）
- 插入排序 — 理解为什么实际中用它处理小数组
- 计数排序 — 理解非比较排序的原理
- 桶排序 — 理解分桶思想
第三梯队（知道即可）
- 冒泡排序 — 作为对比的基准
- 选择排序 — 理解不稳定的原因
- 希尔排序 — 了解增量序列的概念
- 基数排序 — 了解按位排序的思想
常见面试问答
Q：什么是排序的稳定性？为什么重要？
稳定性是指：对于值相同的元素，排序后它们的相对顺序是否与排序前一致。
为什么重要？ 当需要按多个字段排序时（例如先按成绩排序，再按姓名排序），稳定排序可以保留之前的排序结果。不稳定排序会破坏之前的顺序。
Q：为什么比较类排序的下界是 O(n log n)？
n 个元素有 n! 种排列，每次比较最多排除一半的可能性。因此至少需要 $\log_2(n!)$ 次比较，由 Stirling 公式可知 $\log_2(n!) = \Theta(n \log n)$。
Q：快速排序和归并排序如何选择？
| 维度 | 快速排序 | 归并排序 |
|---|---|---|
| 平均速度 | 更快（常数因子小） | 稍慢 |
| 最坏情况 | O(n²) | O(n log n) |
| 稳定性 | 不稳定 | 稳定 |
| 额外空间 | O(log n) | O(n) |
| 缓存友好 | 好（顺序访问） | 较差（需要额外数组） |
结论：一般用快排，需要稳定性时用归并，需要最坏保证时用堆排序。
Q：为什么不用堆排序作为默认排序？
堆排序虽然最坏 O(n log n) 且原地，但缓存命中率低，实际速度比快排慢 2-3 倍。它的价值更多体现在优先队列这一数据结构上。
总结
没有"最好"的排序算法，只有"最合适"的。理解每种算法的特点和适用场景，才能在面试和实际开发中做出正确选择。
记住这个口诀：
- 小规模用插入
- 通用场景用快排
- 要稳定用归并
- 要保底用堆排
- 值域小用计数