E7 排序的性质与比较

对应大纲： 2.1.4-6 排序算法（基本概念、冒泡、选择、插入、计数）+ 初赛会考的快排/归并常识

分量： 排序出现在 12/19 套。初赛考的是性质，不是实现。

📝 S3_计数排序与手写排序.md 讲复赛怎么写；本章讲初赛怎么考。

一、★ 六种排序的性质对照表（背下来）

排序	平均复杂度	最坏	最好	稳定？	额外空间
冒泡排序	$O(n^2)$	$O(n^2)$	$O(n)$ （带提前退出）	✓ 稳定	$O(1)$
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	✗ 不稳定	$O(1)$
插入排序	$O(n^2)$	$O(n^2)$	$O(n)$	✓ 稳定	$O(1)$
快速排序	$O(n\log n)$	$O(n^2)$	$O(n\log n)$	✗ 不稳定	$O(\log n)$ 递归栈
归并排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	✓ 稳定	$O(n)$
计数排序	$O(n+k)$	$O(n+k)$	$O(n+k)$	✓ 稳定	$O(k)$
堆排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	✗ 不稳定	$O(1)$

① 稳定性口诀：「快、选、堆」不稳定，其余都稳定。

CSP 2022 第 12 题问「以下说法错误的是」，答案就是「简单选择排序是稳定的」。

📝 什么叫稳定：值相等的元素，排序后相对顺序不变。 选择排序为什么不稳定：{5a, 5b, 3} 第一轮把最小的 3 和位置 1 的 5a 交换 → {3, 5b, 5a}，两个 5 换位了。

② 只有归并排序需要 $O(n)$ 的额外空间（要开辅助数组合并）。

③ 快速排序最坏是 $O(n^2)$ （每次都选到最大或最小当基准，比如对已排好序的数据用固定基准）。归并排序最坏仍是 $O(n\log n)$ ——这是它们最大的区别。

冒泡排序：相邻两个比较，逆序就交换，大的往后「冒」。

⚠️ 「交换次数 = 逆序对数」是必背结论，因为每交换一次相邻元素恰好消掉一个逆序对。

CSP 2025 第 12 题： $\{6,1,5,2,4\}$ 升序需要几次交换？逆序对： $(6,1)(6,5)(6,2)(6,4)(5,2)(5,4)$ —— 6 个，所以交换 6 次。数逆序对比模拟冒泡快得多。

⚠️ CSP 2020 第 5 题给的伪代码带 FLAG 提前退出机制，问「最少需要多少次比较」→ 数据已有序时只跑一轮 = $n-1$ 。看到「最少 / 最好情况」，就去想「数据已经排好序会怎样」。

排序	怎么做
冒泡	相邻比较、逆序交换，一轮定一个最大值到末尾
选择	每轮从未排序部分选出最小的，和当前位置交换
插入	把当前元素插到前面已排好的部分的正确位置（像理扑克牌）
快排	选一个基准，小的放左、大的放右，再对两半递归（分治）
归并	先把数组对半分、各自排好，再合并两个有序数组（分治）
计数	统计每个值出现几次 → 求前缀和 → 从后往前放回原位

📝 快排和归并都是分治，但方向相反：快排「先分好再递归」（难在分），归并「先递归再合并」（难在合）。

① 统计：cnt[key]++
② 前缀和：cnt[i+1] += cnt[i]
③ 从后往前扫原数组：res[--cnt[key]] = i

⚠️ 第 ③ 步必须从后往前（for (i = n-1; i >= 0; --i)），这样才能保持稳定性。正着走会把相同键值那一组的顺序倒过来。

⚠️ 双关键字计数排序：先排第二关键字，再排第一关键字。 因为计数排序稳定，第二遍会保留第一遍的相对顺序。倒过来做就毁了。（CSP 2019 第 20 题整道题就考这个。）

情形	选什么
数据量小（ $n \le 5000$ ）	随便， $O(n^2)$ 也够
数据量大、值域大	快排 / 归并（竞赛里直接用 `sort`）
值域很小（如 $0\sim10^6$ ）而个数很多	计数排序 $O(n+k)$
要求稳定	归并、插入、冒泡、计数（不能用 `sort`，要用 `stable_sort`）
只要前 $k$ 大	堆 / 部分排序

📝 std::sort 不保证稳定（内部是内省排序 = 快排 + 堆排 + 插排），要稳定必须用 std::stable_sort。这个区别在复赛里也会出事，见 S2_排序的稳定性与原下标技巧.md。

前提：数据必须有序。

写法	用在什么时候
`while (l <= r) { ... r = mid - 1; }`	找确切相等的值
`while (l < r) { ... r = mid; }`	找第一个满足条件的位置（lower_bound 型）

⚠️ right = mid 必须搭配 while (l < r)，否则死循环。 ⚠️ 只有确定 mid 一定不是答案时才能写 mid - 1；如果 mid 本身可能是答案，写 mid - 1 会把它跳过去。

📝 CSP 2023 第 19 题（二分找缺失元素）实测：把 right = mid 改成 right = mid - 1 会漏答案，把 left = mid + 1 改成 left = mid 会死循环。这两个坑各出现了一次。

参考答案