专题 08 排序 · 复习强化

考点：排序问题与关键字（A1）。

（A1）考点：排序 = 把一组记录按关键字的大小关系重新排列；关键字可以是整数、字符串、结构体的某个成员——凡能比大小的皆可。

解析：排序算法与"排的是什么"无关：整数、字符按码值、学生按分数，算法同一套；比的是关键字、动的是整条记录。

排除法：选"只能是整数/字母"的人把载体当成了本质；选"文件的创建日期"的人只是举了一个具体关键字，没回答"排什么"。

考点：升序与降序（A2）。

（A2）考点：非递增 = 每一步不增 = 降序（可相等相邻）：$\{5,2,9,1\}$ 排成 9 5 2 1。

解析：题目术语三兄弟——递增（严格大于）、非递减（允许相等）、非递增（允许相等）；本题"非递增"就是从大到小。

排除法：选 1 2 5 9 的人排成了升序；选 5 2 9 1 的人没排序；选 1 9 2 5 的人乱序。

考点：稳定性的定义（A3）。

（A3）考点：稳定 = 关键字相等的元素排序后相对次序不变——排之前谁在前，排之后还在前。

解析：稳定性与"结果正确"无关（值序都对），只关心相等元素的先后；判断靠"相等时会不会被交换/跨越"。

排除法：选"不死循环"的人把"稳定"理解成了运行可靠；选"一样快"的人理解成了性能一致；选"结果一定正确"的人——正确性是排序的底线，不是稳定性的定义。

考点：稳定性的意义（A4）。

（A4）考点：稳定排序的价值在多关键字排序：先按次要关键字排、再按主要关键字（稳定）排——主要关键字相同者保住第一轮按次要关键字排好的次序（E8 展开）。

解析：不稳定排序第二轮会把第一轮的次序搅乱；先次后主+稳定=一次到位，这是稳定性的实战意义。

排除法：选"更快/更省空间"的人把稳定性当成了性能指标；选"结果好看"的人没抓到场景。

考点：比较类与非比较类（A5）。

（A5）考点：冒泡/快排/插入都靠元素两两比较决策；计数排序靠"值当下标进桶"绕开比较——非比较类。

解析：比较类受 $\Omega(n\log n)$ 下界约束（I6），非比较类（计数）用值域信息换线性速度（E 组展开）。

排除法：冒泡、快排、插入全是比较排序——逐项排除即可。

考点：原地排序（A6）。

（A6）考点：原地排序 = 只用 $O(1)$ 级额外空间、直接在原数组内交换完成；冒泡/选择/插入/快排原地，归并/计数不是。

解析：少量临时变量（如交换用的 t、下标）不算破坏原地；辅助数组才算 $O(n)$ 额外空间。

排除法：选"不能借助任何变量"的人把原地苛刻到无法实现；选"在原来的电脑上"的人望文生义；选"地址段不变"的人把说法与内存管理混淆。

考点：评价排序的维度（A7）。

（A7）考点：评价排序的三大维度：时间复杂度（最好/平均/最坏）、空间复杂度（是否原地）、稳定性。代码行数不是评价指标。

解析：三维度综合看：没有全胜的算法——快排平均快但最坏退化，归并稳定但要辅助空间，选谁看场景（I7/I8）。

排除法：代码长短与算法质量无关——选它的人把可读性指标混进了算法评价。

考点：算法家族总览（A8）。

（A8）考点：平方家族（冒泡/选择/插入）简单直接；$O(n\log n)$ 家族（归并、快排平均、堆排）更快更复杂；计数排序非比较、靠值域桶接近线性。

解析：三档速度对应三类思想：相邻交换/选位插入、分治与堆结构、值域统计；记忆地图先立起来，各组展开。

排除法：选"复杂度都相同"的人没分档；选"计数任何场景首选"的人忽略了值域限制（E3）；选"快排最坏也 $n\log n$"的人混淆了平均与最坏（G5）。

考点：相邻比较交换思想（B1）。

（B1）考点：冒泡 = 从头到尾依次比较相邻两个元素、逆序即交换——每轮把当前最大值"冒"到未排序段末尾。

解析：相邻性是冒泡的身份证：只动邻居、逐轮推进；与选择的"隔空换位"对照（C 组）。

排除法：选最小换最前的是选择排序；插入前缀的是插入排序；分半合并的是归并。

考点：一轮最大沉底（B2）。

（B2）考点：$\{5,3,8,1\}$ 第一轮：$5,3$ 交换得 $\{3,5,8,1\}$；$5,8$ 不换；$8,1$ 交换——结果 3 5 1 8，最大值 $8$ 沉底。

解析：一轮 = $n-1$ 次相邻比较；轮末未排序段的最大值必然到位于末尾，这是冒泡正确性的根基。

排除法：选 1 3 5 8 的人把整场排完了；选 3 1 5 8 的人多跑了一轮（那是两趟的结果）；选原序的人没动手。

考点：趟数与整体流程（B3）。

（B3）考点：标准冒泡最多 $n-1$ 轮内层扫描：$5$ 个元素最多 $4$ 轮——每轮固定一个最大值，剩最后一个自然就位。

解析：轮数上界 $n-1$ 而非 $n$：排好前 $n-1$ 个后最后一个无处可去；带提前退出时实际轮数可能更少（B6）。

排除法：选 $5$ 的人多数了一轮；选 $6$ 的人按 $n(n-1)/2$ 的味道乱猜；选 $3$ 的人少数了（4 个逆序最多需 4 轮收缩）。

考点：时间复杂度（B4）。

（B4）考点：冒泡平均与最坏都是 $O(n^2)$：比较次数约 $n(n-1)/2$，与逆序程度挂钩。

解析：最好情况要靠提前退出优化才到 $O(n)$（B6/B7）；无优化时即使有序也跑满 $n(n-1)/2$ 次比较。

排除法：选 "$n\log n$ 与 $n^2$" 的人把它当成了快排；选 "$n$ 与 $n^2$" 的人默认了带优化；选 "$n^2$ 与 $n^3$" 的人臆造了更坏档。

考点：稳定性（B5）。

（B5）考点：冒泡只对严格大于的相邻对交换，相等对从不交换——相等元素的相对次序保持，冒泡稳定。

解析：稳定性判据就一句话："相等时动不动"；冒泡不动，稳定；选择会隔空换位，不稳定（C4）。

排除法：选"相等可能交换"的人没看严格大于；选"取决于数据"的人稳定性是算法性质与数据无关；选"偶数才稳定"的人无稽之谈。

考点：提前退出优化（B6）。

（B6）考点：每轮记录是否发生过交换，一整轮无交换即整体有序、提前结束——最好情况（已序）首轮就比较 $n-1$ 次收工；但最坏（逆序）每轮都有交换，救不了，仍是 $O(n^2)$。

解析：优化只改善好情况，不改变最坏复杂度；"无交换=有序"是冒泡的重要不变量。（2020 年真题的 FLAG 版冒泡考法）

排除法：选"最坏变 $O(n)$"的人高估了优化；选"比较恒为 $n(n-1)/2$"的人那是无优化版；选"变成稳定排序"的人把性能与稳定性混了。

考点：已序输入比较 n 减 1（B7）。

（B7）考点：已序 $\{1,2,3\}$ + 提前退出：第一轮比 $2$ 次（$n-1$ 次）、零交换、立即结束——总比较 $n-1$。

解析：这是带优化冒泡的最好情况 $O(n)$；若不带优化会继续空跑到 $n(n-1)/2$。

排除法：选 $3$ 的人按无优化算了全程；选 $0$ 的人以为有序就完全不比；选 $6$ 的人把两轮比较翻倍乱算。

考点：逆序输入比较 n(n-1)/2（B8）。

（B8）考点：逆序 $\{3,2,1\}$ 是最坏输入：每轮都有交换、优化失效，比较总数 $n(n-1)/2 = 3$ 次。

解析：完全逆序 = 每一对都比较并交换过；注意本题 $n=3$ 时 $n(n-1)/2 = 3$，与选项 $6$（那是交换+比较混算或 $n=4$ 的值）区分。

排除法：选 $6$ 的人算成了 $n(n-1)$ 或把交换也计入比较；选 $1$、选 $2$ 的人都少数了轮次。

考点：交换次数等于逆序对数（B9）。

（B9）考点：冒泡每次相邻交换恰好消除一个逆序对，总交换次数 = 数组的逆序对数：$\{6,1,5,2,4\}$ 的逆序对是 $6$ 对，交换 $6$ 次。（2025 年 CSP-J 单选真题数据）

解析：$(6,1)(6,5)(6,2)(6,4)(5,2)(5,4)$ 共 $6$ 对；归并排序能在 $O(n\log n)$ 统计逆序对（F11），两法互证。

排除法：选 $5$ 的人漏了一对（常漏 $(5,4)$）；选 $7$ 的人多算；选 $8$ 的人把比较当交换。

考点：一趟后的状态（B10）。

（B10）考点：程序就是冒泡第一趟：$5,3$ 换；$5,8$ 不换；$8,1$ 换——得 3 5 1 8。

解析：读代码逐对跟踪即可；j < 3 恰是 $n-1$ 对相邻比较。

排除法：选 1 3 5 8 的人排到了底；选 3 1 5 8 的人多换了一步；选原序的人没执行交换。

考点：两趟后的状态（B11）。

（B11）考点：第二趟在 3 5 1 8 上比较前 $2$ 对：$3,5$ 不换；$5,1$ 换——得 3 1 5 8，次大值 $5$ 归位倒数第二。

解析：两趟后末两位 $\{5,8\}$ 就位、前两位仍乱——冒泡从右往左逐位"凝固"。

排除法：选 1 3 5 8 的人跑完了全程；选 3 5 1 8 的人只跑了一趟；选 1 5 3 8 的人交换对象搞错。

考点：降序冒泡改法（B12）。

（B12）考点：降序只需把交换条件改为 a[j] < a[j + 1]——"小在前"才交换，大值浮向前。

解析：改一个比较方向就翻转整个序；用 >= 会在相等时也交换，白白破坏稳定性并多做交换。

排除法：选 != 的人相等也换、序全乱；选"多跑一趟"的人方向不变多跑也没用；选 >= 的人破坏了稳定性。

考点：内层边界 n-i-1（B13）。

（B13）考点：第 $i$ 趟后末尾 $i$ 个位置已被前几趟放好最大元素，内层上界 n-1-i 让范围逐趟收缩、已就位元素不再参与。

解析：不写 - i 结果仍正确但白比较已就位段（比较次数翻倍量级不变、常数翻倍）；写成 j < n-1-i 是标准紧凑写法。

排除法：选"提前结束全部循环"的人那是提前退出优化（B6）；选"防负下标"的人那是内层别的防护；选"没作用"的人没看比较次数差异。

考点：交换计数模拟（B14）。

（B14）考点：$\{2,1,3\}$ 只有一对逆序 $(2,1)$：交换 $1$ 次得 1 2 3；第二轮（若跑）无交换。

解析：小数据手模：比较 $2,1$ 交换；比较 $1,3$ 不换——一次交换收工。

排除法：选 $3$ 次的人连不换的也算了；选 $0$ 次的人没看见 $(2,1)$ 逆序；选 $2$ 次结果还错的人把排好的数组又动了。

考点：选最小放最前思想（C1）。

（C1）考点：选择排序每轮在未排序区间选出最小值、与未排序区间第一个位置交换——$n-1$ 轮后整体有序。

解析：选位（找最小）与换位（一次交换）分离：比较很多、交换很少——这是它与冒泡的本质分工差异。

排除法：相邻交换是冒泡；插入前缀是插入排序；分半递归是归并/快排。

考点：比较次数固定（C2）。

（C2）考点：选择排序每轮完整扫描找最小，比较次数与输入无关恒为 $n(n-1)/2$——已序的 $\{1,2,3\}$ 也要比 $3$ 次。

解析：找最小必须看全——不扫完怎么知道谁最小？有序性帮不了它；这与冒泡/插入"数据越有序越快"形成对照（I1）。

排除法：选 $0$ 的人以为有序就免扫；选 $1$、$2$ 的人都按"已序省事"的错觉少算了。

考点：交换次数至多 n-1（C3）。

（C3）考点：每轮至多一次交换（最小值换到首位），$n$ 个元素 $n-1$ 轮——交换次数 $\le n-1$，$100$ 个元素最多 $99$ 次。

解析：$4950 = 100 \times 99/2$ 是比较次数不是交换次数——选择的"多比少换"两笔账分开记。

排除法：选 $4950$ 的人把比较次数当成交换次数；选 $100$ 的人多算一轮；选 $1$ 的人只看了某一轮。

考点：不稳定性实例（C4）。

（C4）考点：$\{5_a, 8, 5_b, 2\}$ 第一轮最小值 $2$ 与首位 $5_a$ 隔空交换：得 2 8 5b 5a——$5_a$ 被甩到 $5_b$ 之后，相等元素次序被破坏，选择排序不稳定（2022 年真题判定项）。

解析：不稳定的根源是"远距离交换"跨越了同值元素；冒泡只动邻居所以稳定（B5）。

排除法：选"次序不变"的人没跟踪身份标记；选 2 5a 8 5b 的人交换对象找错；选"任何数组都不稳定"的人说过了头——不稳定指存在破坏次序的输入，不是每个输入都破坏。

考点：一轮后最小就位（C5）。

（C5）考点：$\{4,1,3,2\}$ 第一轮找最小 $1$（下标 $1$）与首位 $4$ 交换：得 1 4 3 2。

解析：只有首位置换；未排序段 $\{4,3,2\}$ 内部次序保持原样（这是选择不稳定的原因之一）。

排除法：选全序的人跑完了整场；选原序的人没执行交换；选 1 3 2 4 的人把整段都动了。

考点：选最大放末尾（C6）。

（C6）考点：变体"每轮选最大放末尾"：$\{3,1,2\}$ 最大 $3$（已在首位）与末位 $2$ 交换——得 2 1 3。

解析：镜像变体：凝固方向从右端开始；首元素恰是最大时也要与末位交换（除非重合）。

排除法：选 1 3 2 的人以为"已在首位就不用换"——位置约定是末尾，必须换；选 1 2 3、原序的人执行错了对象。

考点：与冒泡对比（C7）。

（C7）考点：选择排序的招牌优势：交换次数至多 $n-1$，远少于冒泡的逐对交换——数据移动代价大的场景（如大结构体）占优；但比较次数两者同量级、选择还不吃"基本有序"的红利。

解析：冒泡多换少省心、选择多比少换位；各记一笔账（I1 汇总对比）。

排除法：选"比较更少"的人两者比较同量级；选"交换更多"的人恰好反了；选"复杂度更低"的人都是 $O(n^2)$。

考点：一轮后的状态（C8）。

（C8）考点：$\{5,2,8,1\}$ 第一轮最小 $1$（下标 $3$）与首位 $5$ 交换：得 1 2 8 5。

解析：注意 $2$ 恰好在正确位置附近但没被动过——选择只保证"最小就位"，不管其他元素的次序。

排除法：选 2 5 8 1 的人交换成相邻对换了；选 1 5 8 2 的人把 $5$ 放错了位；选全序的人跑完了全程。

考点：排序结果模拟（C9）。

（C9）考点：$\{5,2,8,1\}$ 完整选择排序的最终结果当然是 1 2 5 8。

解析：任何正确的排序算法结果都相同——差异全在过程与开销；本题顺手验证模拟熟练度。

排除法：选 5 8 2 1 的人排成降序；1 2 8 5 是只跑一轮的中间态；2 1 5 8 的人过程混乱。

考点：交换次数模拟（C10）。

（C10）考点：$\{4,1,3,2\}$ 选择排序：轮 $1$ 换 $4,1$；轮 $2$ 换 $4,2$（最小 $2$）；轮 $3$ 最小 $3$ 已位不换——共 $2$ 次。

解析：交换计数看"最小值是否恰在待排首位"：在则免换；本题只有第三轮免。

排除法：选 $3$ 的人把"已位免换"那轮也算了；选 $4$ 的人超过上限 $n-1=3$ 更不对；选 $6$ 的人把比较次数混了进来。

考点：抽牌插入思想（D1）。

（D1）考点：插入排序 = 摸牌整理：手牌（前缀）始终有序，每摸一张（下一个元素）在有序手牌中找位插入。

解析：生活原型最贴近的排序；"前缀有序、逐个吸收"是它的不变量（D2）。

排除法：抽最小放前是选择；相邻交换是冒泡；分半合并是归并。

考点：已序前缀与待插元素（D2）。

（D2）考点：插入排序的循环不变量：前缀始终有序、后段是待处理元素——每步把后段第一个插入前缀，有序区逐步长大。

解析：与前段原序无关（会移动插入）、与后段无关；不变量是理解正确性与分析复杂度的抓手。

排除法：选"前缀保持原样"的人忽略了插入会挪动前缀元素；选"完全无序"的人说反了；选"两端有序中间乱"的人那是另一种想象。

考点：时间复杂度（D3）。

（D3）考点：插入排序平均与最坏 $O(n^2)$：每个元素平均要挪过前缀的一半。

解析：最坏 = 完全逆序，每个新元素一路挪到最前（D10）；最好 = 已序，一路不挪（D4）。

排除法：选"$n\log n$ 与 $n^2$"的人按快排记忆；选"$n$ 与 $n^2$"的人把最好当成了平均；选"$n^3$"的人臆造。

考点：最好情况（D4）。

（D4）考点：已序 $\{1,2,3,4\}$：每个新元素只与前缀末尾比一次、零移动——移动次数 $0$，接近 $O(n)$。

解析：插入的"零移动好情况"无需专门优化代码、天然成立（冒泡要加提前退出才有）；这就是基本有序数据选它的底气（D11）。

排除法：选 $3$ 的人把比较次数当成了移动；选 $6$ 的人按最坏 $n(n-1)/2$ 算；选 $4$ 的人多数了一项。

考点：稳定性（D5）。

（D5）考点：内层仅对严格大于待插元素的后移，相等者不动、待插元素落在相等者之后——后出现的排在后面，次序保持，插入排序稳定。

解析：又是"相等时动不动"判据：插入不动相等者（后移条件 > 不是 >=），稳定。

排除法：选"被打乱"的人没看严格大于；选"取决于数据"的人稳定性是算法固有性质；选"逆序才稳定"的人无据。

考点：后移腾位实现（D6）。

（D6）考点：a[j + 1] = a[j] 把比待插元素大的项逐个后移一位，为待插元素腾出位置——挪的是前缀里的"大个子"。

解析：方向从右往左逐个覆盖，腾出的空位最后由 a[j+1] = t 补上；这是插入排序的核心三行。

排除法：选"把待插元素后挪"的人挪反了对象；选"交换相邻"的人没看是赋值不是 swap；选"删除"的人无中生有。

考点：内层 while 条件（D7）。

（D7）考点：j >= 0 防左越界：待插元素比前缀所有元素都小时，扫描会走到最左端，没有该条件就读 a[-1]。

解析：短路顺序 j >= 0 在前、a[j] > t 在后——先保证下标合法再取值（与 06 卷网格判界同理）。

排除法：选"加快循环"的人它不提速只保命；选"保证稳定性"的人那是严格大于的功劳；选"可删掉"的人删了就埋越界雷。

考点：一步后的状态（D8）。

（D8）考点：$\{3,1,2\}$ 第一步插入 $1$：$3$ 后移、$1$ 落首——得 1 3 2。

解析：一步只处理一个元素；前缀 $\{1,3\}$ 有序、尾部 $2$ 待理。

排除法：选 1 2 3 的人跑完了；选原序的人没插入；选 2 1 3 的人插错了元素。

考点：两步后的状态（D9）。

（D9）考点：接 1 3 2 第二步插入 $2$：$3$ 后移、$2$ 插中间——得 1 2 3，$3$ 个元素两步完成。

解析：$n$ 个元素恰好 $n-1$ 步；本题两步收工，无需第三步。

排除法：选 1 3 2 的人只走了一步；选 2 1 3、3 1 2 的人插入位置找错。

考点：逆序输入移动次数（D10）。

（D10）考点：完全逆序 $\{5,4,3,2,1\}$：第 $i$ 个元素要挪过前面全部 $i-1$ 个——总移动 $1+2+3+4 = 10$（即 $n(n-1)/2$）。

解析：逆序输入 = 每步都触发最深移动；移动次数与冒泡的交换次数同为 $10$——两种口径度量同一份"乱度"。

排除法：选 $5$ 的人只算了单层；选 $15$ 的人把比较也混进或按 $n(n-1)$ 算；选 $4$ 的人只看了最后一步。

考点：基本有序数据最适用（D11）。

（D11）考点：三种平方排序中，插入排序独享"基本有序就近线性"红利（每元素挪几步就位）；选择不吃数据形态、冒泡要靠优化才能沾光。

解析：实战里 sort 内部对小区间也换用插入收尾——工业实现都认这个特性（I8）。

排除法：选选择的人比较次数恒定、沾不到红利；选冒泡的人不带优化时空跑到 $n(n-1)/2$；选"完全一样"的人无视三者的数据敏感性差异。

考点：值域桶思想（E1）。

（E1）考点：计数排序开一个覆盖值域的桶数组，统计每个值出现次数，再按值序倒出——全程不比较元素大小。

解析：值即下标：cnt[v] 记值 $v$ 的个数；顺序由下标天然给出，比较被"数格子"取代。

排除法：递归分区是快排、相邻交换是冒泡、取堆顶是堆排——三者都比大小。

考点：复杂度 n 加值域（E2）。

（E2）考点：计数排序时间 $O(n + V)$（$n$ 个元素各进桶一次、$V$ 个桶各倒一次）+ 空间 $O(V)$。

解析：$n$ 与 $V$ 谁大看谁；值域小（如百分制分数）时近似线性飞快。

排除法：$O(n\log n)$ 是比较类挡位；$O(n^2)$ 是平方家族；$O(V\log V)$ 无此算法。

考点：值域限制（E3）。

（E3）考点：计数排序的命门是值域：桶数组要开 $V$ 个——值域 $10^{18}$ 的 long long 直接出局；$10^6$ 以内、百分制、几十种字符都是好场景。

解析：判适合与否第一问"值多大、多稠密"；值大数少时比较排序才是正道。

排除法：$10^6$ 以内整数、$0\sim100$ 分数、几十种字符都开得起桶；唯独 $10^{18}$ 值域开不出。

考点：统计代码（E4）。

（E4）考点：cnt[a[i]]++ 一遍统计：$\{3,1,3,2,1\}$ 得 $cnt = \{0,2,1,2\}$——$3$ 出现 $2$ 次，cnt[3] 是 $2$。

解析：统计是计数排序第一阶段；桶下标与值一一对应（值 $v$ 的计数在 cnt[v]）。

排除法：选 $1$ 的人数的是 $2$ 的个数；选 $3$ 的人把值当成了计数；选 $5$ 的人给的是总元素数。

考点：正序扫描输出（E5）。

（E5）考点：按值从小到大、每个值输出 cnt[v] 次：$\{3,1,3,2,1\}$ → 1 1 2 3 3。

解析：这是朴素版（不保同值元素身份次序）；要稳定需倒序填充版（E6）。

排除法：选原序的人没做输出阶段；选 1 2 3 的人去重了（E9 才去重）；选 3 3 2 1 1 的人倒着扫桶。

考点：倒序填充稳定版（E6）。

（E6）考点：稳定版计数排序：先对 cnt 求前缀和，再从后往前扫描原数组，每个元素放进其值的当前位置、位置减一——后扫的同值元素占靠前格子，先扫的留在后面，次序保持。

解析：稳定计数是多关键字排序的地基（E8）；"倒扫+位置递减"是保序的全部机关。

排除法：正序填充的人同值次序反转；先反转数组的人答非所问；"天生稳定"的人朴素版恰恰丢了身份次序。

考点：前缀和定位（E7）。

（E7）考点：cnt 求前缀和后，cnt[v] = 值 $\le v$ 的元素总数 = 值 $v$ 在输出数组中可占用的最后一个位置。

解析：每个值分到一段连续位置：从"次数"到"末位置"，前缀和完成了从计数到定位的升级。

排除法：选"出现次数"的人那是求和前；选"值的下标"的人混淆概念；选"值域大小"的人把总量当成了定位。

考点：双关键字先次后主（E8）。

（E8）考点：双关键字 $(a,b)$ 排序：先按次要关键字 $b$ 排，再按主要关键字 $a$ 排——第二轮用稳定排序，$a$ 相同者保住第一轮 $b$ 的次序。（2019 年完善程序真题骨架：先第二关键字再第一关键字）

解析：顺序颠倒（先主后次）会让第二轮覆盖第一轮成果；稳定+先次后主 = 一次到位，正是稳定性存在的意义（A4）。

排除法：选"先主后次一次即可"的人次序被第二轮搅乱；选"同时比较"的人那就成了三路比较不是两趟计数；选"先 $b$ 再 $a$ 恰好错误"的人恰好说反——那正是正确顺序。

考点：去重输出（E9）。

（E9）考点：桶 $\{cnt[1]{=}2, cnt[2]{=}1, cnt[3]{=}2\}$ 去重输出 = 每个非空桶各一次：1 2 3。

解析：计数排序改输出规则即得去重升序——"桶非空"就是"值出现过"；比哈希去重+排序两步更直接。

排除法：选 1 1 2 3 3 的人没去重；选 3 2 1 的人倒序扫桶；选 1 3 的人漏了非空桶 $2$。

考点：负数偏移（E10）。

（E10）考点：负值域用偏移平移：$-50 \sim 50$ 统一加 $50$ 映射到 $0 \sim 100$，桶照开、输出时减回去。

解析：桶下标必须非负——平移是标准解法；这与 07 卷"值当下标"的映射思想一脉相承。

排除法：选"不能排"的人没想起平移；选"负下标数组"的人 C++ 不支持；选"改成 0"的人把真实数据篡改成了 $0$，值全错。

考点：分治思想（F1）。

（F1）考点：归并排序 = 分治：分到单元素（天然有序），治=逐层把两个有序段合并成更长有序段，$\log n$ 层合并回整体。

解析：分而治之的两半各交给递归；"先拆到底、回溯合并"的节奏与快排"先分区再递归"相反。

排除法：基准分区是快排；选最小换前是选择；扔桶是计数。

考点：递归框架（F2）。

（F2）考点：归并递归三步：msort(l, mid) 排左半 → msort(mid+1, r) 排右半 → merge 合并两半。

解析：递归到单元素返回（F9），回溯时自底向上两两合并；框架顺序"先递归后合并"。

排除法：选"一步完成无递归"的人那只是一次 merge；选"先 merge 再递归"的人半段还没序就合没意义；选"只递归左半"的人另一半没人管。

考点：合并两个有序段（F3）。

（F3）考点：双下标取小合并 $\{1,4,6\}$ 与 $\{2,3,5\}$：$1,2,3,4,5,6$ 依次出列——1 2 3 4 5 6。

解析：两段各一个指针，每轮较小的出列、指针前移；一段空了另一段整段接上。

排除法：选拼接原序的人没合并；选"右段在前"的人方向反；选 1 2 4 3 5 6 的人中途取错了段。

考点：合并比较次数（F4）。

（F4）考点：$\{1,4,6\}$ 与 $\{2,3,5\}$ 合并比较 $5$ 次：$1{vs}2$、$4{vs}2$、$4{vs}3$、$4{vs}5$、$6{vs}5$——最后剩 $6$ 免比直接接上。

解析：比较次数 $\le (两段长之和 - 1)$：每比较一次至少出列一个元素，最后剩的那个免比。

排除法：选 $3$ 的人只数了一段的指针；选 $4$ 的人漏了 $4{vs}5$ 那次；选 $6$ 的人把免比的尾巴也算了。

考点：时间复杂度（F5）。

（F5）考点：归并排序最好、平均、最坏全是 $O(n \log n)$：拆分固定 $\log n$ 层、每层合并共 $O(n)$，与数据无关。

解析：分区平衡（永远对半）是它的定海神针——对比快排的分区随基准波动（G5）；"最坏也稳"是它的招牌。

排除法：选最好 $O(n)$ 的人把它当成了插入；选最坏 $O(n^2)$ 的人把它当成了快排；选"无法确定"的人低估了它。

考点：辅助数组（F6）。

（F6）考点：合并要同时读两段、按序写入——原地挪动会覆盖还没读的数据，所以先把合并结果写进 $O(n)$ 临时数组，再整体拷回。

解析：这是归并唯一的空间开销；交换类排序（冒泡/选择/快排）无此需求。

排除法：选"递归必须开数组"的人递归只耗栈；选"为了稳定"的人稳定靠相等取左（F7）；选"编译不通过"的人无稽之谈。

考点：稳定性细节相等取左（F7）。

（F7）考点：合并遇相等取左段（<=）——左段元素原位置更靠前，先出列即保持原次序；这个 = 正是归并稳定的关键。

解析：改成 < 相等时右段先出，稳定性立刻被破坏；一字之差定稳定性。

排除法：选"减少比较"的人方向反（不减少比较）；选"写 < 完全相同"的人丢了稳定性；选"让它不稳定"的人说反。

考点：递归层数（F8）。

（F8）考点：$n=8$ 对半拆到单元素：$8 \to 4 \to 2 \to 1$，共 $3$ 层（$\log_2 8 = 3$）。

解析：层数 = $\lceil \log_2 n \rceil$；每层合并总量 $O(n)$，层数乘出 $O(n\log n)$（F5 的来源）。

排除法：选 $8$ 的人把元素数当层数；选 $7$ 的人按 $n-1$ 记；选 $4$ 的人多算了一层（拆到 $1$ 为止）。

考点：终止条件（F9）。

（F9）考点：递归终止于"区间只剩一个元素"（l >= r）——单元素天然有序，开始向上合并。

解析：终止条件写错（如漏掉）会无限递归；单元素有序是归并正确性的起点。

排除法：选"长度小于 $4$"的人还能再拆两层；选"数组有序时"的人归并不检查整体有序；选"深度到 $10$"的人魔法数字。

考点：排序结果模拟（F10）。

（F10）考点：$\{5,2,4,1\}$ 归并排序：拆 $\{5,2\}|\{4,1\}$ → 各自合并成 $\{2,5\}|\{1,4\}$ → 顶层合并 1 2 4 5。

解析：先在纸上画递归树再自底向上合并；小数组手模两遍，考场遇到就是送分。

排除法：选 5 4 2 1 的人倒序了；2 5 1 4 是中间态；4 1 2 5 的人底层合并错。

考点：归并统计逆序对（F11）。

（F11）考点：合并时若右段元素 $R[j]$ 出列而左段还剩 $k$ 个，这 $k$ 个都大于 $R[j]$ 且原下标更靠前——恰好贡献 $k$ 个逆序对。$\{3,1,2\}$ 的逆序对是 $2$ 个：$(3,1)$、$(3,2)$。（提高级经典应用，初赛了解思想）

解析：一次归并顺带数完逆序对，$O(n\log n)$——与冒泡交换次数互证（B9 同为 $6$ 的那组数据）。

排除法：选 $3$ 的人把 $(1,2)$ 也算逆序（值序反了才行）；选 $1$ 的人漏 $(3,2)$；选 $0$ 的人没找对。

考点：与快排对比（F12）。

（F12）考点：归并：稳定、要 $O(n)$ 辅助空间、最坏稳 $O(n\log n)$；快排：平均更快、原地、但最坏退化 $O(n^2)$ 且不稳定。

解析：两大 $n\log n$ 算法互补：要稳定要保险用归并，要平均速度省内存用快排；std::sort 是快排底子的introsort（G8）。

排除法：选"都稳定都原地"的人两头全错；选"快排最坏 $n\log n$、归并最坏 $n^2$"的人全反；选"平均复杂度不同"的人两者平均同为 $O(n\log n)$。

考点：基准分区思想（G1）。

（G1）考点：快排每轮：选基准，把小于它的挪左、大于它的挪右（分区），基准恰好落在最终位置；再对左右两区递归。

解析：分区的副产品是"基准落位"——每轮至少一个元素到达最终位置；递归边界+分区是快排全部。

排除法：相邻交换是冒泡；对半拆是归并；取堆顶是堆排。

考点：一次分区后的状态（G2）。

（G2）考点：以首元素 $4$ 为基准分区 $\{4,2,5,1,3\}$：小于 $4$ 的 $\{2,1,3\}$ 居左、$4$ 落位、$\{5\}$ 居右——得 2 1 3 4 5。

解析：分区只保证"左小右大、基准归位"，左右各自内部仍无序（左区 2 1 3 还没排）——递归继续处理。

排除法：选全序 1 2 3 4 5 的人把递归也跑完了；选 5 3 1 2 4 的人把大的放左边了；选原序的人没分区。

考点：基准落位下标（G3）。

（G3）考点：分区结果 2 1 3 4 5 中基准 $4$ 落在下标 $3$（$0$ 起）——左区 $3$ 个元素正好都小于它。

解析：基准下标 = 小于基准的元素个数；它是本轮唯一确定最终位置的元素。

排除法：选 $2$ 的人少算了左区一个；选 $4$ 的人数到了右端；选 $0$ 的人以为基准不动。

考点：平均复杂度（G4）。

（G4）考点：快排平均 $O(n \log n)$——平均意义下分区大致平衡，递归深度约 $\log n$。

解析：注意只是平均：最坏 $O(n^2)$（G5）；快排的速度优势来自常数小、缓存友好，实战均速常胜归并。

排除法：选 $O(n^2)$ 的人那是它的最坏；选 $O(n)$ 的人把它当成了计数；选 $O(n\log^2 n)$ 的人无此挡位。