主题
十大经典排序算法对比
1. 为什么需要一页“横向比较”
前面的排序主章和图解页更强调“把单个算法讲透”。但真正到做题、面试、工程选型时，难点往往不是“某个算法会不会写”，而是：
- 为什么这里该选归并，不该选快排。
- 为什么这里宁可用计数排序，也不做比较排序。
- 为什么数据近乎有序时，插入排序反而不差。
- 为什么系统库里经常混合使用多种排序策略。
所以这一页专门解决“横向比较”的问题。
2. 十大经典排序算法总表
| 算法 | 平均复杂度 | 最坏复杂度 | 空间复杂度 | 稳定性 | 原地 | 核心思想 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n^2) | O(1) | 稳定 | 是 | 相邻交换，大数后沉 |
| 选择排序 | O(n^2) | O(n^2) | O(1) | 不稳定 | 是 | 每轮选最小值 |
| 插入排序 | O(n^2) | O(n^2) | O(1) | 稳定 | 是 | 把当前元素插入已排序区 |
| 希尔排序 | 视步长而定 | O(n^2) | O(1) | 不稳定 | 是 | 分组插入，逐步缩小间隔 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 否 | 分治拆分，有序合并 |
| 快速排序 | O(n log n) | O(n^2) | 递归栈 | 不稳定 | 近似原地 | 基准划分 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 | 是 | 维护堆顶最值 |
| 计数排序 | O(n+k) | O(n+k) | O(k) | 稳定 | 否 | 统计频次直接定位 |
| 桶排序 | 平均 O(n+k) | 取决于桶内排序 | 取决于桶数 | 视实现而定 | 否 | 按范围分桶 |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(n+r) | 稳定 | 否 | 按位分配，多轮稳定排序 |
说明：
k常表示值域大小或桶数。d表示位数。r表示基数，如十进制排序时的10。