Appearance
排序算法对比与性能实测
如何选择合适的排序算法
408 排序章节有近十种排序算法，每种都有自己的时间复杂度、空间复杂度、稳定性。考试中最常见的出题方式就是对比分析：
- 选择题："对基本有序序列，以下排序算法中效率最高的是？"
- 选择题："以下排序算法中，不稳定的有哪些？"
- 综合题："给定场景，选择最合适的排序算法并分析复杂度"
这篇把所有算法横向对比，方便集中复习。
十大排序算法总览
比较类排序
比较类排序通过元素之间的比较来决定顺序，理论下界为 O(n log n)（考试常考）。
| 算法 | 最好时间 | 平均时间 | 最坏时间 | 空间 | 稳定性 |
|---|---|---|---|---|---|
| 直接插入排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 折半插入排序 | O(n log n) | O(n²) | O(n²) | O(1) | 稳定 |
| 希尔排序 | — | 约 O(n^1.3) | O(n²) | O(1) | 不稳定 |
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 简单选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
希尔排序的复杂度取决于增量序列的选择。常见结论：使用 Hibbard 增量（1, 3, 7, 15...）时最坏 O(n^1.5)；实际应用中平均约 O(n^1.3)。408 一般不要求精确推导，但"最坏不超过 O(n²)"和"优于简单插入排序"这两点常考。注意它是不稳定的。
非比较类排序
非比较类排序利用数据的特殊性质（如整数的位），可以突破 O(n log n) 下界。
| 算法 | 时间复杂度 | 空间 | 稳定性 | 适用条件 |
|---|---|---|---|---|
| 基数排序 | O(d × (n + r)) | O(r) | 稳定 | 关键字可拆分为 d 位，每位 r 种取值 |
d = 关键字位数，r = 基数（如十进制 r=10），n = 记录数。
408 高频考点速查
考点一：稳定性判断
口诀：快选希堆不稳定，其余全稳定。
- 不稳定：快速排序、简单选择排序、希尔排序、堆排序
- 稳定：直接插入、折半插入、冒泡、归并、基数
判断稳定性的本质：排序过程中是否可能把相同关键字的两个元素的相对位置颠倒。
考点二：最好/最坏情况分析
| 场景 | 最快的算法 | 原因 |
|---|---|---|
| 数据基本有序 | 直接插入排序 O(n) | 内层循环几乎不执行 |
| 数据基本有序 | 冒泡排序 O(n) | 第一趟无交换直接终止 |
| 数据完全逆序 | 快排退化为 O(n²) | 每次 partition 只分出 1 个元素 |
| 需要最坏情况也是 O(n log n) | 归并排序、堆排序 | 不受数据分布影响 |
408 选择题经典问法："对关键字基本有序的序列，以下排序方法中效率最高的是？" → 直接插入排序。
考点三：空间复杂度
| 空间复杂度 | 算法 |
|---|---|
| O(1) | 插入、冒泡、选择、希尔、堆排序 |
| O(log n) | 快速排序（递归栈深度） |
| O(n) | 归并排序 |
| O(r) | 基数排序 |
快排的空间复杂度是 O(log n)（平均）到 O(n)（最坏），取决于 partition 的划分是否均匀。
考点四：比较次数与移动次数
| 算法 | 比较次数（最好） | 比较次数（最坏） | 移动次数（最好） | 移动次数（最坏） |
|---|---|---|---|---|
| 直接插入 | n-1 | n(n-1)/2 | 0 | n(n-1)/2 |
| 冒泡排序 | n-1 | n(n-1)/2 | 0 | 3n(n-1)/2 |
| 简单选择 | n(n-1)/2 | n(n-1)/2 | 0 | 3(n-1) |
值得注意的几点：
- 简单选择排序的比较次数始终是 n(n-1)/2，与初始序列无关
- 冒泡排序每次交换需要 3 次赋值（temp = a; a = b; b = temp），插入排序每次移动只需 1 次赋值（a[j+1] = a[j]）
- 所以同为 O(n²)，插入排序的实际速度约为冒泡排序的 3-5 倍
考点五：排序趟数与初始序列的关系
| 算法 | 排序趟数是否与初始序列有关 |
|---|---|
| 直接插入排序 | 无关，固定 n-1 趟 |
| 冒泡排序 | 有关，已有序时 1 趟即可终止 |
| 简单选择排序 | 无关，固定 n-1 趟 |
| 快速排序 | 有关，取决于 partition 的递归深度 |
| 堆排序 | 无关 |
| 归并排序 | 无关，固定 ⌈log₂n⌉ 趟 |
考点六：适用场景选择
| 场景 | 推荐算法 | 原因 |
|---|---|---|
| n 较小 (< 50) | 直接插入排序 | 常数因子小，代码简单 |
| 数据基本有序 | 直接插入排序 | 最好 O(n) |
| n 较大，要求平均性能最优 | 快速排序 | 平均 O(n log n)，常数因子小 |
| n 较大，要求最坏也是 O(n log n) | 堆排序或归并排序 | 不会退化 |
| 需要稳定排序 | 归并排序 | 唯一稳定的 O(n log n) 比较排序 |
| 关键字位数少、值域小 | 基数排序 | O(d(n+r))，线性时间 |
| 数据量极大，内存不足 | 外部排序（归并排序） | 支持外存数据处理 |
实测对比：性能增长曲线
理论复杂度是渐进分析，实际性能还取决于常数因子和数据分布。
下面的工具在你的浏览器中实时运行七种排序算法，从 n=50 到 n=50000，绘制耗时、比较次数、交换次数的增长曲线。你可以切换不同的数据分布（随机、已排序、逆序、基本有序），亲自验证上面每一条理论结论：
试试这几个实验
实验一：随机数据 + 耗时
观察 O(n²)（冒泡、选择、插入）和 O(n log n)（快排、归并、堆排序）的分离——前者呈抛物线增长，后者几乎是一条平线。n=50000 时，冒泡排序约 4275ms，快排仅 5.5ms，差距达 777 倍。
实验二：已排序数据 + 耗时
验证考点二：插入排序和冒泡排序变为 O(n)，耗时骤降到 < 1ms。但选择排序仍然超过 1 秒——因为它的比较次数始终是 n(n-1)/2，与数据是否有序无关。
"基本有序序列用直接插入排序"——配合这张图理解，比背结论好使。
实验三：随机数据 + 交换/移动次数
验证考点四：冒泡和插入的交换/移动次数在数量级上相同（约 6.2 亿次），但插入排序的实际耗时只有冒泡的 1/5。原因正是"交换 = 3 次赋值，移动 = 1 次赋值"。
实验四：已排序数据 + 交换/移动次数
冒泡、插入、选择、希尔的交换/移动次数全部为 0。但选择排序依然慢——因为它做了 12.5 亿次比较。这直观说明了比较次数和移动次数对性能的影响是独立的。
实验五：逆序数据 + 耗时
验证最坏情况：冒泡和插入都退化到 O(n²) 最坏值。而 O(n log n) 算法不受影响，这就是所谓的"最坏情况保证"。
比较类排序的下界
为什么比较类排序最快也只能 O(n log n)？
n 个元素有 n! 种排列。每次"比较"只能得到两种结果（是/否），因此可以画一棵判定树（二叉树），叶节点对应所有可能的排列。
- 叶节点数 ≥ n!
- 高度 h 的二叉树最多有 2^h 个叶节点
- 因此 h ≥ log₂(n!)
由 Stirling 公式：log₂(n!) = Θ(n log n)
所以任何基于比较的排序算法，最坏情况下至少需要 Ω(n log n) 次比较。
408 真题考过这个证明过程，判定树 + Stirling 公式的推导思路值得看一下。
总结：一句话记住每种排序
| 算法 | 一句话 |
|---|---|
| 直接插入 | 基本有序时最快，小规模首选 |
| 折半插入 | 减少比较次数，但移动次数不变 |
| 希尔排序 | 插入排序的增量版，突破 O(n²) |
| 冒泡排序 | 最直观的交换排序，有序时 1 趟终止 |
| 快速排序 | 平均最快，但最坏退化为 O(n²) |
| 简单选择 | 比较次数固定，与数据无关 |
| 堆排序 | 原地 + 最坏 O(n log n)，但不稳定 |
| 归并排序 | 稳定 + 最坏 O(n log n)，但需要 O(n) 空间 |
| 基数排序 | 不比较，按位分配，线性时间 |
| 外部排序 | 数据太大放不进内存时的唯一方案 |
考前口诀：
- 不稳定 → 快选希堆
- 最好 O(n) → 插入、冒泡
- 最坏也 O(n log n) → 归并、堆排序
- 空间 O(1) → 插入、冒泡、选择、希尔、堆
- 比较次数与初始序列无关 → 简单选择、归并