排序算法分类与复杂度总览
排序：程序员的基本功
排序是算法中最基础的问题，也是面试中出现频率最高的话题之一。
但排序算法种类繁多：冒泡、选择、插入、归并、快速、堆排、计数、桶排、基数……
它们有什么区别？什么时候该用哪个？
今天，让我们系统性地梳理排序算法家族。
排序算法全景图
排序算法
├── 比较排序
│ ├── O(n²) 类
│ │ ├── 冒泡排序
│ │ ├── 选择排序
│ │ └── 插入排序
│ ├── O(n log n) 类
│ │ ├── 归并排序
│ │ ├── 快速排序
│ │ └── 堆排序
│ └── 其他
│ └── 希尔排序
└── 非比较排序
├── 计数排序
├── 桶排序
└── 基数排序复杂度总览
| 排序算法 | 平均时间 | 最坏时间 | 空间 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 希尔排序 | O(n^1.3) | 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 + k) | O(n²) | O(n + k) | 稳定 |
| 基数排序 | O(nk) | O(nk) | O(n + k) | 稳定 |
什么是「稳定」的排序？
稳定性指的是排序后相同元素的相对顺序是否保持不变。
不稳定排序示例:
原始: [2₁, 1, 2₂]
排序后: [1, 2₂, 2₁] ← 2 的相对顺序变了！
稳定排序示例:
原始: [2₁, 1, 2₂]
排序后: [1, 2₁, 2₂] ← 2 的相对顺序保持什么时候需要稳定性？
当排序的元素不只是数字，而是有多个属性时。
例如按成绩排序后，再按姓名排序——如果排序不稳定，姓名排序会打乱成绩排序的结果。
如何选择排序算法？
按数据量选择
| 数据量 | 推荐算法 | 原因 |
|---|---|---|
| n ≤ 50 | 插入排序 | 小数据量时常数小 |
| n ≤ 10000 | 快速排序 | 综合性能最优 |
| n 非常大 | 外部排序 | 内存装不下 |
按数据特点选择
| 数据特点 | 推荐算法 | 原因 |
|---|---|---|
| 基本有序 | 插入排序 | 有序时接近 O(n) |
| 完全随机 | 快速排序 | 综合性能最优 |
| 有范围限制 | 计数/桶/基数 | 可达线性时间 |
| 需要稳定 | 归并排序 | 稳定的 O(n log n) |
| 需要最坏情况 | 堆排序/归并排序 | 最坏也是 O(n log n) |
按空间限制选择
| 空间限制 | 推荐算法 |
|---|---|
| O(1) | 堆排序、希尔排序、选择排序 |
| O(log n) | 快速排序（递归栈） |
| O(n) | 归并排序、计数排序、桶排序、基数排序 |
排序算法的「三足鼎立」
在面试中最常被问到的三种排序算法是：快速排序、归并排序、堆排序。
为什么是这三个？
- 都是 O(n log n)：渐近时间复杂度最优
- 各有特点：快速排序实际最快，归并排序稳定，堆排序最稳定（最坏情况）
- 延伸问题多：partition、三路划分、Top K、手写堆……
各算法的特点
冒泡排序
- 最简单，但效率最低
- 适合教学，不适合实际使用
- 优化：提前终止 + 记录最后交换位置
选择排序
- 交换次数最少（最多 n 次）
- 但无论数据如何都是 O(n²)
- 不稳定
插入排序
- 小数据量和基本有序时效率高
- 实际排序中，经常在快速排序的递归到小数据量时切换到插入排序
- 稳定
希尔排序
- 插入排序的改进版
- 通过「跳跃式」插入减少比较次数
- 不稳定
归并排序
- 稳定 + 最坏 O(n log n)
- 但需要额外 O(n) 空间
- 适合外部排序（磁盘文件分段读入）
快速排序
- 实际应用中最快
- 但最坏情况 O(n²) 需要优化（随机 pivot、三数取中等）
- 不稳定
堆排序
- 不需要递归，用数组直接实现
- 最坏情况也是 O(n log n)
- 不稳定
计数排序
- 适用于范围小的整数排序
- 时间 O(n)，但空间取决于数据范围
- 稳定
桶排序
- 适用于数据均匀分布
- 平均 O(n)，最坏 O(n²)
- 稳定
基数排序
- 适用于整数或字符串排序
- 按位稳定排序，k 为位数
- 稳定
总结
排序算法的选择取决于多种因素：
- 数据规模：小数据用插入排序，大数据用快速/归并/堆排序
- 数据特点：基本有序用插入排序，有范围用计数/桶/基数
- 稳定性要求：需要稳定用归并排序
- 空间限制：空间紧张用堆排序/插入排序
- 最坏情况：需要保证最坏性能用堆排序/归并排序
没有最好的排序算法，只有最适合场景的排序算法。
面试追问方向
- 什么是排序的稳定性？举例说明稳定和不稳定的排序
- 快速排序的最坏情况是什么？如何优化？
- 为什么说归并排序适合外部排序（磁盘排序）？
- 堆排序的空间复杂度是多少？它是原地排序吗？
- 计数排序、桶排序、基数排序的适用场景是什么？