先看复杂度与稳定性
| 算法 | 平均 | 最坏 | 额外空间 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 插入排序 | O(n²) | 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²)。
- 最坏情况也不能退化：堆排序，代价是常数更大而且不稳定。
一个容易忽略的点
很多语言标准库里的排序并不是单一算法，而是混合策略：数据量小的时候退化成插入排序，规模大了再切到快速排序或归并排序。所以实际写代码时先看标准库，不必急着手写。
小结
选排序先问三个问题：数据规模多大、需不需要稳定、最坏情况能不能接受。想清楚这三件事，选择基本就定下来了。
