【算法图解】排序算法大比拼：什么时候用哪个
冒泡/快排/归并/堆排/计数排序到底怎么选？本文用“稳定性、时间上界、空间、数据特征、工程约束”五个维度做对比，并给出面试可复述的选择逻辑。
18 分钟阅读
小明
【算法图解】排序算法大比拼：什么时候用哪个
排序算法你可能学过一堆：
- 冒泡/选择/插入
- 快排/归并/堆排
- 计数/桶/基数
但一到工程/面试问“怎么选”，很多人就只会说：
快排平均快。
这不够。
真正的选择要看约束：
- 你要不要稳定？
- 你更怕最坏情况还是平均情况？
- 内存紧不紧？
- 数据有没有特殊结构（值域小、近似有序、重复多）？
这篇文章给你一个可复用的决策框架。
1. 先记住 5 个维度
- 稳定性：相等元素相对顺序是否保持
- 时间复杂度（平均/最坏）：你能否接受退化
- 空间复杂度：能否开辅助空间
- 数据特征：是否近似有序、重复多、值域小
- 工程约束：语言内置实现、栈深度、安全性
2. 一张“面试可复述”的对比表
| 算法 | 稳定 | 平均时间 | 最坏时间 | 额外空间 | 适用场景 |
|---|---|---|---|---|---|
| 冒泡 | ✅ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 教学/小数据/近似有序（带早停） |
| 归并 | ✅ | $O(n\log n)$ | $O(n\log n)$ | $O(n)$ | 需要稳定 + 上界稳定 |
| 快排 | ❌ | $O(n\log n)$ | $O(n^2)$ | $O(\log n)$ | 平均快、内存友好（需防退化） |
| 堆排 | ❌ | $O(n\log n)$ | $O(n\log n)$ | $O(1)$ | 要上界稳定 + 原地 |
| 计数 | ✅（稳定实现） | $O(n+k)$ | $O(n+k)$ | $O(k)$ | 整数值域小、可接受空间 |
（注：快排空间一般指递归栈平均 $O(\log n)$。）
3. 你真正要掌握的是“选择逻辑”
3.1 先问：要稳定吗？
- 要稳定：优先归并（或计数/基数在条件满足时）
- 不要稳定：进入下一步
3.2 再问：能接受最坏 O(n²) 吗？
- 不能：堆排 / 归并 / introsort（快排 + 退化保护）
- 能：快排通常是默认首选
3.3 再问：内存紧吗？
- 很紧：堆排、快排（原地）
- 不紧：归并更稳（稳定 + 上界稳定）
3.4 最后看数据特征
- 近似有序：插排（小规模）或 Timsort（许多语言内置）
- 重复很多：三路快排（Dutch National Flag partition）
- 值域很小：计数排序
4. 工程现实：你多半用的是内置排序
很多语言的内置排序不是“纯快排”。
常见策略：
- 快排 + 退化保护（introsort）
- 归并变体
- Timsort（利用 runs，近似有序非常快）
面试里你可以顺带体现工程理解：
- “我知道语言内置排序通常做了退化保护，不是教材里的朴素实现。”
5. 面试一问一答（可直接用）
- 为什么快排平均快？
- 因为分区后递归深度期望为 $\log n$，并且原地操作常数小。
- 快排最坏为什么慢？怎么避免？
- pivot 选择退化导致不平衡划分；用随机 pivot/三数取中/三路快排/退化切堆排。
- 什么时候选堆排？
- 需要 $O(n\log n)$ 上界稳定 + 原地内存。
- 什么时候选计数？
- 数据是整数且值域 $k$ 可控，愿意用 $O(k)$ 空间换时间。
总结
排序怎么选，不靠背算法名，靠约束：
- 稳定性
- 时间上界
- 内存
- 数据特征
- 工程约束
如果你愿意，我可以再补一篇：三路快排（重复值多时的“快排救星”）。