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 操作衍生出逆序对、链表排序等经典问题
- 堆排序 — 重点在堆这个数据结构本身，Top K、优先队列都离不开它
实用算法
- 插入排序 — TimSort 的核心组件，小数组和近乎有序数据的最优选择
- 计数排序 — 非比较排序的代表，值域小时效率极高
- 桶排序 — 理解分桶思想，很多工程问题的优化都用到类似策略
基础算法
- 冒泡排序 — 最直观的排序，适合作为理解其他算法的起点
- 选择排序 — 理解不稳定性的最佳案例
- 希尔排序 — 增量序列的概念，突破 O(n²) 的一种思路
- 基数排序 — 按位排序，字符串和大整数场景下的利器
实测对比：性能增长曲线
理论复杂度只是渐进分析，实际性能还取决于常数因子。下面的工具在你的浏览器中实时运行七种排序算法，从 n=50 到 n=10000 绘制性能增长曲线：
几个值得关注的现象
切换不同数据分布试试：
- 随机数据：O(n²) 算法和 O(n log n) 算法的差距一目了然——前者的曲线呈抛物线增长，后者几乎是平的
- 已排序数据：插入排序 O(n) 碾压所有算法；冒泡排序也是 O(n)；但注意观察希尔排序的表现
- 逆序数据：冒泡排序和插入排序都是最坏情况 O(n²)，但插入排序的移动次数约为冒泡交换次数的同一量级（每次移动只需 1 次赋值 vs 交换的 3 次赋值）
- 基本有序：插入排序接近 O(n)，快速排序仍然保持 O(n log n)
切换纵轴指标试试：
- 「耗时」看实际运行速度，受 JS 引擎优化影响
- 「比较次数」看算法本质的工作量
- 「交换/移动次数」看数据搬运的开销
为什么插入排序比冒泡排序快？
从实测数据可以看到，两者都是 O(n²)，但插入排序的实际操作量更少：
| 冒泡排序 | 插入排序 | |
|---|---|---|
| 每次交换的赋值次数 | 3 次（temp = a; a = b; b = temp） | 1 次（a[j+1] = a[j]） |
| 平均比较次数 | 约 n²/2 | 约 n²/4 |
| 内层循环 | 每趟扫描整个未排序区间 | 找到位置就停 |
这就是为什么 TimSort 在小数组上选择插入排序而不是冒泡排序。
常见问答
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 倍。它的价值更多体现在优先队列这一数据结构上。
总结
没有"最好"的排序算法，只有"最合适"的。理解每种算法的特点和适用场景，才能做出正确选择。
记住这个口诀：
- 小规模用插入
- 通用场景用快排
- 要稳定用归并
- 要保底用堆排
- 值域小用计数