初赛专题（八）：排序、查找与复杂度分析 —— 量级、稳定性、逆序对与二分

本讲定位：★ 高频。七年真题统计（见 cspj-exam-analysis-2019-2025.md）：排序查找类选择题约每年 1~2 题（稳定性 2022、逆序对 = 冒泡交换次数 2025、找最大的比较下界 2021、二分次数 2019/2024）；更要紧的是二分查找连续三年进完善程序（2021 矩形计数、2022 求平方根、2023 找缺失数），边界收缩写法是挖空重灾区。本讲是”知识 + 能力”双属性：前半部分手算（量级排序、稳定性表、模拟排序过程），后半部分读写代码（二分模板必须默写级掌握）。从本讲起，课程重心开始向”读程序、写程序”倾斜。

前置知识：第 02 讲的 $2^k$ 数感（二分次数）；第 06 讲的完全二叉树（堆排序的”堆”、二分的决策树）；第 12 讲的递归（归并/快排的递归结构，读懂即可）。

适合对象：CSP-J 初赛。标注 ⭐ 的小节为进阶内容，第一遍学习可以跳过。

1. $O$ 记号与量级速查

$O$ 记号刻画的是运行时间随 $n$ 增长的速度，忽略常数与低阶项：$3n^2 + 5n + 7$ 就是 $O(n^2)$。初赛必背的量级链（从快到慢）：

$$ O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) $$

看循环数量级的基本功（第 09 讲会深化成完整方法论）：

代码形态 复杂度 记忆点
单层循环跑到 $n$ $O(n)$
两层嵌套各跑到 $n$ $O(n^2)$ 内层跑到 $i$ 也是 $O(n^2)$（求和 $\frac{n(n-1)}{2}$）
i *= 2 或每轮折半 $O(\log n)$ 翻倍/折半 = 对数
外层 $n$、内层折半 $O(n \log n)$ 归并、快排、堆排的量级

由数据范围反推可行算法（完善程序选思路时的”作弊表”，按一秒约 $10^8$ 次基本运算估）：

$n$ 的规模 可接受的复杂度 对应算法举例
$n \le 20$ $O(2^n)$ 枚举子集、搜索
$n \le 500$ $O(n^3)$ 三重循环
$n \le 5000$ $O(n^2)$ 冒泡/插入/选择排序、双重循环
$n \le 10^5$ $O(n \log n)$ 归并/快排、sort、二分
$n \le 10^7$ $O(n)$ 一遍扫描、计数排序

例 1：$n = 10^5$ 的数组用冒泡排序要约 $10^{10}$ 次操作——超时百倍；换 $O(n \log n)$ 的 sort 约 $1.7 \times 10^6$，绰绰有余。“这段程序对 $n = 10^5$ 能否在时限内出解”就按这两张表判断。

2. 八大排序总表：复杂度与稳定性

稳定性：排序后相等元素的相对次序不变，则称稳定。总表必背（★ 标出真题直接考过的格子）：

排序 平均 最坏 最好 稳定性 一句话特征
冒泡 $O(n^2)$ $O(n^2)$ $O(n)$★（带 FLAG） 稳定 相邻交换，交换次数 = 逆序对数★
插入 $O(n^2)$ $O(n^2)$ $O(n)$ 稳定 新牌插进手里的有序牌；近乎有序时飞快
选择 $O(n^2)$ $O(n^2)$ $O(n^2)$ 不稳定★ 每轮选最小放前面；比较次数固定 $\frac{n(n-1)}{2}$
归并 $O(n \log n)$ $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(n \log n)$ $O(n \log n)$ 不稳定 用完全二叉树（第 06 讲编号）维护最值
计数 $O(n + w)$ $O(n + w)$ $O(n + w)$ 稳定★ 不比较、按值开桶；$w$ 是值域大小
基数 $O(d(n + w))$ 同左 同左 稳定 按低位到高位逐位计数排序，$d$ 是位数

三个必考记忆点：

  1. 不稳定的只有三个：选择、快排、堆排——“选快堆不稳”五个字背下来，其余全稳定。2022 年真题即考”选择排序不稳定”。
  2. 选择排序为什么不稳定（判断题要能举反例）：$[3_a, 3_b, 1]$ 第一轮选出最小的 $1$ 与 $3_a$ 交换，得 $[1, 3_b, 3_a]$——两个 3 的次序反了。
  3. 稳定性有什么用（2019 完善程序原型）：双关键字排序——先按次关键字排一遍，再按主关键字稳定排一遍，次关键字的序被保留，等价于一次双关键字排序。用不稳定排序做第二遍，第一遍就白排了。

⭐ 比较类排序的极限是 $O(n \log n)$（决策树深度），计数/基数能更快是因为它们不做比较、直接按值分桶——这也是”计数排序不属于比较排序”这类判断题的依据。