第 13 章 排序 · 知识细节练习

考点：排序的定义（A1）。

解析：排序 = 按关键字（数值、字典序、优先级等）把一组元素重排成升序或降序。✅ 正确

排除法：无（判断题）。混淆点：排序的对象是"记录"，关键字只是排序依据——记录本身要跟着移动。

关联 · 升序与降序（A2）：方向由比较符号决定。

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

解析：升序 = 小的在前：{3,1,4,1,5} → 1 1 3 4 5（相等元素相邻排）。正确答案 A。

排除法：B 是降序；C 是原数组；D 只排了前三个、后两个还是乱序。

关联 · 降序冒泡（I5）：把比较方向翻转即可得降序。

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

解析：稳定性 = 关键字相等的元素排序前后相对顺序不变。例如按"成绩"排序，两个 90 分的同学在名单里的先后不变。✅ 正确

排除法：无（判断题）。混淆点：稳定性只关乎相等元素，与"不相等元素谁前谁后"无关。

关联 · 稳定排序清单（G4）：冒泡/插入/归并/计数稳定。

考点：比较排序与非比较排序（A4）。

解析：冒泡、选择、插入、快排、归并、堆排序都靠"元素两两比较"决定顺序；计数排序统计每个值出现次数、不比较元素。正确答案 C。

排除法：A、B、D 都是比较排序。

关联 · 比较排序的下界（G6）：比较排序最坏至少 $O(n \log n)$，计数排序可 $O(n + k)$。

考点：原地排序（A5）。

解析：原地（in-place）= 除输入数组外只使用 $O(1)$ 额外空间（几个循环变量）。冒泡/选择/插入/堆排序是原地；归并要 $O(n)$ 辅助数组、不是原地。正确答案 A。

排除法：B 是归并排序的空间；C、D 无对应算法。

关联 · 归并的空间与稳定性（E7）：$O(n)$ 辅助数组换稳定性。

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

解析：三大维度：时间复杂度（快不快）、空间复杂度（省不省内存）、稳定性（相等元素次序保不保）。✅ 正确

排除法：无（判断题）。混淆点：常数因子也影响实际速度（插入排序在小数据上比快排快），但复杂度分析是主线。

关联 · 排序算法的选择（G7）：按场景选算法，三个维度一起权衡。

考点：冒泡的基本思想（B1）。

解析：每轮从前往后比较相邻元素，逆序就交换；一轮结束，当前最大元素"冒"到未排部分的末尾。✅ 正确

排除法：无（判断题）。混淆点：冒泡只交换相邻元素——这正是它稳定的原因（B4）。

关联 · 冒泡第一轮的结果（B2）：一轮只保证最大值就位。

考点：冒泡第一轮的结果（B2）。

解析：{5,3,8,1,7} 第一轮：$5>3$ 换、$5<8$ 不换、$8>1$ 换、$8>7$ 换 → 3 5 1 7 8，最大 8 已到末尾。正确答案 A。

排除法：B 是完整排序结果；C 是部分反向；D 是只交换了第一对。

关联 · 冒泡两趟后的状态（I6）：第 k 轮后末尾 k 个元素就位。

考点：冒泡的时间复杂度（B3）。

解析：优化版在已有序时一轮无交换即退出 → 最好 $O(n)$；逆序时比较 $(n-1)+(n-2)+\cdots+1 = O(n^2)$。正确答案 A。

排除法：B 把最好情况记成 $O(n \log n)$；C 忽略了优化；D 把最坏记成 $O(n \log n)$。

关联 · 冒泡的提前结束优化（B5）：最好 $O(n)$ 来自提前退出。

考点：冒泡的稳定性（B4）。

解析：相等元素之间不满足 >，不会交换 → 相对顺序不变 → 稳定。✅ 正确

排除法：无（判断题）。混淆点：只要交换条件用 >（或 <）而不是 >=（或 <=），相等就不换。

关联 · 稳定性的判断依据（H1）：只交换相邻元素是稳定的常见特征。

考点：冒泡的提前结束优化（B5）。

解析：swapped 标志：一轮中没发生任何交换说明已有序，立即结束。已有序数组只跑 1 轮、比较 $n-1$ 次 → $O(n)$。✅ 正确

排除法：无（判断题）。混淆点：无优化版即使有序也跑满 $n-1$ 轮、$O(n^2)$。

关联 · 冒泡优化的趟数（I4）：基本有序数组 2 趟就完成。

考点：冒泡的趟数（B6）。

解析：每趟至少就位 1 个元素（最大值），$n$ 个元素最多 $n-1$ 趟；$n=5$ 时最多 $4$ 趟。正确答案 A。

排除法：B 多算一趟；C 少算；D 把趟数当成总比较次数。

关联 · 冒泡的趟数（I 组）：外层循环 i < n - 1 就是趟数。

考点：选择的基本思想（C1）。

解析：每轮扫描未排序部分找出最小元素，与未排序部分的第一个位置交换 → 放到已排序部分的末尾。✅ 正确

排除法：无（判断题）。混淆点：每轮只做一次"隔空"交换——这是它与冒泡的最大区别（C4）。

关联 · 选择的比较与交换次数（C2）：交换 $O(n)$、比较 $O(n^2)$。

考点：选择的比较与交换次数（C2）。

解析：比较次数固定 $n(n-1)/2$（与输入无关）；交换最多 $n-1$ 次（每轮至多一次）。正确答案 A。

排除法：B 把交换也记成 $O(n^2)$；C/D 张冠李戴。

关联 · 选择的比较次数（J5）：$n=4$ 时比较 $3+2+1=6$ 次。

考点：选择的不稳定性（C3）。

解析：{2, 2, 1} 升序：第一轮最小是 1（下标 2），与下标 0 的 2 交换 → 1 2 2，两个 2 的相对顺序颠倒。✅ 正确

排除法：无（判断题）。混淆点：交换跨越了相等元素，就可能破坏稳定。

关联 · 不稳定排序清单（G5）：选择是三大不稳定排序之一。

考点：选择与冒泡的对比（C4）。

解析：选择每轮只交换 1 次，总交换 $O(n)$；冒泡每次逆序都交换，最坏 $O(n^2)$。比较次数两者都是 $O(n^2)$。正确答案 A。

排除法：B——比较次数同量级；C——复杂度相同；D——选择不稳定。

关联 · 选择的交换次数（J2）：{5,3,8,1,7} 只交换 3 次。

考点：选择第 i 轮就位（C5）。

解析：第 $i$ 轮把全局第 $i$ 小的元素放到下标 $i-1$，之后不再动 → 前 $i$ 个元素是最终结果。✅ 正确

排除法：无（判断题）。混淆点：插入排序的前缀只是"暂时有序"，会再变（D5）——这是两排序的经典区别。

关联 · 插入的前缀有序（D5）：选择"就位"、插入"暂序"。

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

解析：每轮选最大放到末尾与选最小放最前完全对称，最终同样是升序。正确答案 A。

排除法：B 是"选最大放最前"才会得的降序；C、D 无依据。

关联 · 选最大放末尾（J4）：i 从 n-1 递减，找 [0, i] 中最大。

考点：插入的基本思想（D1）。

解析：像抓牌：新元素（key）与已有序前缀从右往左比较，比 key 大的后移，key 落位在正确位置。✅ 正确

排除法：无（判断题）。混淆点：插入是"边比较边移动"，与选择"先找再换"不同。

关联 · 插入的移动实现（D6）：移动就是为 key 腾位置。

考点：插入的时间复杂度（D2）。

解析：已有序时内层 while 一次都不进 → $O(n)$；逆序时每轮移动 $1+2+\cdots+(n-1)$ 次 → $O(n^2)$。正确答案 A。

排除法：B 把最好记成 $O(n \log n)$；C 忽略最好情况；D 无依据。

关联 · 已有序的移动次数（K5）：有序输入移动 0 次。

考点：插入的稳定性（D3）。

解析：内层条件是 a[j] > key（严格大于），相等元素不移位、key 落在相等元素的后面 → 稳定。✅ 正确

排除法：无（判断题）。混淆点：把条件改成 >= 就破坏稳定性。

关联 · 归并的稳定性细节（M7）：合并条件 <= 与 < 的同款细节。

考点：插入的适用场景（D4）。

解析：插入排序在"基本有序"或"数据量小"时表现极佳（移动少、常数小）——这也是快排/归并递归到小区间时切换到插入排序的原因。正确答案 A。

排除法：B 是插入的最坏输入；C 交给 $O(n \log n)$ 算法；D 与排序无关。

关联 · 排序算法的选择（G7）：小数据/基本有序 → 插入。

考点：插入的前缀有序（D5）。

解析：第 $i$ 轮后前 $i$ 个元素有序，但不保证是最终结果——后面更小的元素还会插入到它们前面。✅ 正确

排除法：无（判断题）。混淆点：选择排序第 $i$ 轮后前 $i$ 个已就位（C5），插入排序只是暂时有序。

关联 · 选择第 i 轮就位（C5）：两排序的前缀性质对比。

考点：插入的移动实现（D6）。

解析：内层循环结束时 j 指向第一个 <= key 的位置（或 -1），key 应放在 j + 1。正确答案 A。

排除法：B/C 只在边界巧合；D 无依据。

关联 · 插入排序输出结果（K1）：a[j + 1] = key 是落位语句。

考点：快排的基本思想（E1）。

解析：分治三件套：选基准 → 分区（小的在左、大的在右）→ 对左右子区间递归。✅ 正确

排除法：无（判断题）。混淆点：分区后基准落在最终位置，之后不再参与递归。

关联 · 一次分区后的状态（L1）：分区函数的代码实现。
大纲注：本细节属提高级大纲【5/6】，按用户教学规划保留（J 复赛必备扩展）。

考点：快排的时间复杂度（E2）。

解析：平均每次分区把问题一分为二 → $O(n \log n)$；最坏每次分区只排除基准自身（如已有序 + 固定首元素基准）→ $O(n^2)$。正确答案 A。

排除法：B 忽略最坏；C 忽略平均；D 说反。

关联 · 快排的最坏情况（H2）：最坏情况的触发条件。
大纲注：本细节属提高级大纲【5/6】，按用户教学规划保留（J 复赛必备扩展）。

考点：快排的不稳定性（E3）。

解析：分区时元素隔空交换，相等元素的相对顺序可能被颠倒 → 不稳定。✅ 正确

排除法：无（判断题）。混淆点：稳定性与"分区写法"无关，任何常规分区都可能隔空换位。

关联 · 不稳定排序清单（G5）：快排是三大不稳定排序之一。
大纲注：本细节属提高级大纲【5/6】，按用户教学规划保留（J 复赛必备扩展）。

考点：快排的空间开销（E4）。

解析：快排是原地分区（$O(1)$ 额外空间），额外开销来自递归调用栈：平均 $O(\log n)$、最坏 $O(n)$。正确答案 A。

排除法：B 是归并的空间；C 无依据；D 忽略递归栈。

关联 · 快排的递归深度（L4）：已有序时栈深 $n-1$。
大纲注：本细节属提高级大纲【5/6】，按用户教学规划保留（J 复赛必备扩展）。

考点：归并的基本思想（E5）。

解析：分治：先递归把左右两半各自排好，再把两个有序段合并成一个有序段。✅ 正确

排除法：无（判断题）。混淆点：归并是"先排序后合并"（自顶向下），合并时两半必须已有序。

关联 · 合并两个有序段（M1）：merge 的代码实现。
大纲注：本细节属提高级大纲【5/6】，按用户教学规划保留（J 复赛必备扩展）。

考点：归并的时间复杂度（E6）。

解析：每层合并总代价 $O(n)$，共 $\log_2 n$ 层 → $O(n \log n)$，且与输入无关（无最好最坏之分）。正确答案 A。

排除法：B 是 $O(n^2)$ 家族的复杂度；C 是一层合并的代价；D 是层数。

关联 · 归并的层数（H4）：$8$ 个元素分 $3$ 层。
大纲注：本细节属提高级大纲【5/6】，按用户教学规划保留（J 复赛必备扩展）。

考点：归并的空间与稳定性（E7）。

解析：合并需要 $O(n)$ 辅助数组（tmp）；合并时相等元素先取左边 → 稳定。✅ 正确

排除法：无（判断题）。混淆点：稳定性来自"相等先取左"（M7），空间来自 tmp 数组（M6）。

关联 · 归并的辅助数组（M6）：原地合并会覆盖未处理数据。
大纲注：本细节属提高级大纲【5/6】，按用户教学规划保留（J 复赛必备扩展）。

考点：堆排序的基本思想（F1）。

解析：建堆 → 反复"堆顶与末尾交换 + 向下调整"，$n-1$ 次后数组升序（大根堆）或降序（小根堆）。✅ 正确

排除法：无（判断题）。混淆点：建堆后数组不是有序的，只是满足堆序（N7）。

关联 · 建堆后的数组（N7）：{3,8,1,9,2,7} 建堆后 9 8 7 3 2 1。
大纲注：本细节属提高级大纲【5/6】，按用户教学规划保留（J 复赛必备扩展）。

考点：堆排序的复杂度（F2）。

解析：建堆 $O(n)$ + $n-1$ 次"取堆顶 $O(\log n)$"= $O(n \log n)$；原地交换，额外空间 $O(1)$。正确答案 A。

排除法：B 复杂度错；C 空间错；D 忽略了取堆顶的对数代价。

关联 · 堆排序的输出（N6）：小根堆依次取顶即升序。
大纲注：本细节属提高级大纲【5/6】，按用户教学规划保留（J 复赛必备扩展）。

考点：堆排序的不稳定性（F3）。

解析：建堆的隔层交换与"堆顶↔末尾"的远距离交换都会打乱相等元素顺序 → 不稳定。✅ 正确

排除法：无（判断题）。混淆点：堆排序是唯一"$O(n \log n)$ + $O(1)$ + 不稳定"的组合，性价比高。

关联 · 不稳定排序清单（G5）：堆排序是三大不稳定排序之一。
大纲注：本细节属提高级大纲【5/6】，按用户教学规划保留（J 复赛必备扩展）。

考点：计数排序的基本思想（F4）。

解析：统计每个可能值出现次数，按值从小到大、每个值输出其次数遍。不比较元素。✅ 正确

排除法：无（判断题）。混淆点：计数数组大小 = 值域（最大值 + 1），不是数据个数。

关联 · 计数排序输出（N1）：值域 $0 \sim 8$ 的输出过程。
大纲注：本细节属提高级大纲【5/6】，按用户教学规划保留（J 复赛必备扩展）。

考点：计数排序的复杂度（F5）。

解析：统计 $O(n)$ + 输出 $O(n + k)$（要扫一遍值域）→ $O(n + k)$，$k$ 为值域大小。正确答案 A。

排除法：B 是比较排序的复杂度；C 无依据；D（$O(nk)$）无依据。

关联 · 计数排序的适用与稳定（F6）：$k$ 太大就不划算。
大纲注：本细节属提高级大纲【5/6】，按用户教学规划保留（J 复赛必备扩展）。

考点：计数排序的适用与稳定（F6）。

解析：适合整数且值域小（如成绩 $0 \sim 100$）；配合前缀和（pos 数组）可以做到稳定。✅ 正确

排除法：无（判断题）。混淆点：值域 $10^9$ 时计数数组开不出来，改用其他排序。

关联 · 前缀和定位起始（N3）：pos[v] = 值 v 的起始输出位置。
大纲注：本细节属提高级大纲【5/6】，按用户教学规划保留（J 复赛必备扩展）。

考点：sort 函数与自定义比较器（F7）。

解析：sort(a, a + n) 默认升序；第三参数传比较器实现降序或按关键字排序——初赛完善程序多次考"排序 + 贪心/二分"的组合。✅ 正确

排除法：无（判断题）。混淆点：比较器返回 true 表示"第一个参数应排在第二个之前"。

关联 · 补全排队接水（O3）：O3 里的 less<int>() 就是比较器参数。
大纲注：本细节属提高级大纲【5/6】，按用户教学规划保留（J 复赛必备扩展）。

考点：三种 O(n²) 排序（G1）。

解析：冒泡、选择、插入的最坏复杂度都是 $O(n^2)$（比较或移动次数 $n(n-1)/2$ 级别）。正确答案 A。

排除法：B 是 $O(n \log n)$ 家族；C 是 $O(n + k)$ 级别；D 是 $O(n \log n)$ 家族。

关联 · 冒泡的时间复杂度（B3）：三个 $O(n^2)$ 各有最好情况差异。

考点：平均 O(n log n) 家族（G2）。

解析：快排（平均）、归并、堆排序平均都是 $O(n \log n)$。正确答案 A。

排除法：B 是 $O(n^2)$ 家族；C 中插入是 $O(n^2)$、计数是 $O(n+k)$；D 插入排序是 $O(n^2)$，不属于本家族。

关联 · 最坏 O(n log n) 的排序（G3）：平均与最坏要分开看。

考点：最坏 O(n log n) 的排序（G3）。

解析：归并（固定分层）、堆排序（固定 $n-1$ 次取顶）最坏也是 $O(n \log n)$；快排最坏会退化 $O(n^2)$。正确答案 A。

排除法：B 中快排/冒泡最坏 $O(n^2)$；C 全是 $O(n^2)$；D 是 $O(n+k)$。

关联 · 快排的时间复杂度（E2）：快排"平均优秀、最坏翻车"。

考点：稳定排序清单（G4）。

解析：稳定清单：冒泡、插入、归并、计数。正确答案 A。

排除法：B 全是三大不稳定；C 混入选择/快排；D 混入堆排序。

关联 · 不稳定排序清单（G5）：与本题互为镜像，背成一组。

考点：不稳定排序清单（G5）。

解析：选择（隔空交换）、快排（分区交换）、堆排序（堆顶交换）——三大不稳定。✅ 正确

排除法：无（判断题）。混淆点：计数排序可以做成稳定（前缀和版），别把它算进不稳定。

关联 · 稳定排序清单（G4）：稳定清单 = 冒泡/插入/归并/计数。

考点：比较排序的下界（G6）。

解析：比较排序最坏至少 $O(n \log n)$（决策树论证）；计数排序不做比较，可做到 $O(n)$ 级别。✅ 正确

排除法：无（判断题）。混淆点："突破下界"靠的是放弃比较，不是更聪明的比较。

关联 · 比较排序与非比较排序（A4）：两大类别的根本分野。

考点：排序算法的选择（G7）。

解析：$n = 10^6$ 时 $O(n^2)$ 约 $10^{12}$ 步、$O(n \log n)$ 约 $2 \times 10^7$ 步——必须选快排/归并（或 sort）。正确答案 A。

排除法：B/C/D 都是 $O(n^2)$，$10^6$ 规模直接超时。

关联 · 插入的适用场景（D4）：小数据/基本有序才轮得到 $O(n^2)$。

考点：稳定性的判断依据（H1）。

解析：隔空交换（不相邻元素直接互换）或"相等元素被越过"都会破坏稳定；插入只做相邻后移、相等时不越过 → 稳定。正确答案 A。

排除法：B（选择）隔空交换；C（快排）分区交换；D（堆）堆顶交换——全是隔空换位。

关联 · 选择的不稳定性（C3）：{2,2,1} 的隔空交换实例。

考点：快排的最坏情况（H2）。

解析：已有序 + 固定首元素基准 → 每次分区基准落到端点，只排除 1 个元素 → 递归 $n$ 层、$O(n^2)$。正确答案 A。

排除法：B（随机）恰恰是防退化的手段；C（取中位数）也是好基准；D（三分区）处理全相等很快。

关联 · 随机基准防退化（L6）：随机/三数取中打破最坏输入。
大纲注：本细节属提高级大纲【5/6】，按用户教学规划保留（J 复赛必备扩展）。

考点：计数排序的值域限制（H3）。

解析：计数数组大小 = 值域（最大值 + 1）；值域高达 $10^9$ 时数组开不下，计数排序不可用。正确答案 A。

排除法：B/C 错——不是"稍慢"或"是整数就行"，是数组根本开不出；D 荒谬（$10^9$ 规模下应改用 $O(n \log_2 n)$ 的比较排序）。

关联 · 计数排序的复杂度（F5）：$O(n + k)$ 里 $k$ 太大就不划算。

考点：归并的层数（H4）。

解析：$8 \to 4+4 \to 2 \times 4 \to 1 \times 8$，分裂 $\log_2 8 = 3$ 层（每层合并总代价 $O(n)$，所以总 $O(n \log n)$）。正确答案 A。

排除法：B 把层数当元素数；C 多算一层；D 少算一层。

关联 · 归并的时间复杂度（E6）：层数 × 每层代价 = 复杂度。
大纲注：本细节属提高级大纲【5/6】，按用户教学规划保留（J 复赛必备扩展）。

考点：排序结论综合判断（H5）。

解析：四句全部正确：稳定 = 冒泡/插入/归并/计数；不稳定 = 选择/快排/堆；归并最坏 $O(n \log n)$ 且稳定；快排平均 $O(n \log n)$、最坏 $O(n^2)$。✅ 正确

排除法：无（判断题）。混淆点：这套"复杂度 × 稳定性"总表是 CSP-J 每年必考点，逐条背熟。

关联 · 复杂度与稳定性总表（G1~G6）：本组前六题已逐条展开。

考点：冒泡排序输出结果（I1）。

解析：双层循环 $n-1$ 趟、每趟相邻比较逆序交换，最终升序 1 3 5 7 8。正确答案 A。

实现要点：冒泡框架 = 外层趟数 i < n-1 + 内层 j < n-1-i（每趟少比较一个已就位的）。手算技巧：一轮一轮写数组状态，末尾元素逐轮固定。

排除法：B 是降序结果；C 是原数组；D 顺序错乱。

关联 · 冒泡的基本思想（B1）：框架就是思想的直译。

考点：冒泡的交换次数（I2）。

解析：逐轮数：第 1 轮换 3 次（5↔3、8↔1、8↔7）、第 2 轮 1 次（5↔1）、第 3 轮 1 次（3↔1）、第 4 轮 0 次 → 共 5 次。正确答案 A。

实现要点：交换计数题 = 在 swap 处 cnt++。手算画每轮状态：{5,3,8,1,7} → 3 5 1 7 8 → 3 1 5 7 8 → 1 3 5 7 8 → 不变。

排除法：B（4）漏数第 3 轮；C（6）多数；D（8）是趟数×2 的误解。

关联 · 冒泡的趟数（B6）：交换次数与趟数不是一回事。

考点：冒泡一趟后的状态（I3）。

解析：{9,2,7,4,1} 第一趟：9↔2、9↔7、9↔4、9↔1 → 2 7 4 1 9，最大值 9 冒到末尾。正确答案 A。

实现要点：单趟 = 只跑内层循环一次。手算：想象大元素像气泡连续向右移动，一路换到底。

排除法：B 是完整排序结果；C 漏了 9 与 4 的交换；D 是降序方向。

关联 · 冒泡第一轮的结果（B2）：同款题的概念版。

考点：冒泡优化的趟数（I4）。

解析：{1,2,3,5,4}：第 1 趟交换 5↔4 后排好；第 2 趟无交换、swapped 变假 → 退出。共 2 趟。正确答案 A。

实现要点：优化 = swapped 标志 + 外层条件 i < n-1 && swapped。手算看"最后一次交换发生在第几趟"，该趟后还需一趟确认无交换。

排除法：B（4）是无优化版的趟数；C（1）只算到交换那趟；D 无依据。

关联 · 冒泡的提前结束优化（B5）：提前退出的来源。

考点：降序冒泡（I5）。

解析：比较条件改成 a[j] < a[j+1]（逆序=左小右大）→ 每轮把最小"冒"到末尾 → 降序 5 4 3 1 1。正确答案 A。

实现要点：升序改降序只动一个符号：> 改 <。手算验证边界：两个 1 相等不交换（稳定）。

排除法：B 是升序结果；C 是原数组；D 只有部分排好。

关联 · 升序与降序（A2）：方向由比较符决定。

考点：冒泡两趟后的状态（I6）。

解析：{4,2,5,1,3} 第 1 趟 → 2 4 1 3 5；第 2 趟（比较 3 次）→ 2 1 3 4 5。末尾 5、4 已就位。正确答案 A。

实现要点：第 k 趟后末尾 k 个元素就位。手算逐趟写状态，注意内层范围每趟减 1。

排除法：B 是三趟后的结果；C 是第 1 趟后的状态；D 交换次序错。

关联 · 冒泡一趟后的状态（I3）：单趟与多趟的递进。

考点：选择排序输出结果（J1）。

解析：每轮选最小放最前：1→最前、3→第二位、5→第三位、7→第四位 → 1 3 5 7 8。正确答案 A。

实现要点：选择框架 = 外层 i 定位置 + 内层打擂台找 [i, n-1] 最小值下标 p + swap(a[i], a[p])。手算：每轮圈出最小元素与其落点。

排除法：B 是降序；C 只排了前两个；D 是原数组。

关联 · 选择的基本思想（C1）：框架 = 思想的直译。

考点：选择的交换次数（J2）。

解析：第 1 轮换（5↔1）、第 2 轮 p==i 不换、第 3 轮换（8↔5）、第 4 轮换（8↔7）→ 共 3 次。正确答案 A。

实现要点：if (p != i) 才交换——最小元素恰好已在原位时不换。手算逐轮列出 p 与交换动作。

排除法：B（4）把 p==i 那轮也算上；C（5）是冒泡的交换次数（I2）；D 漏一轮。

关联 · 选择的比较与交换次数（C2）：交换至多 $n-1$ 次。

考点：选择一轮后的状态（J3）。

解析：{9,2,7,4,1} 第一轮打擂台得最小 1（下标 4），与 a[0] 交换 → 1 2 7 4 9。正确答案 A。

实现要点：单轮 = 找 p + 一次交换。手算：圈出最小元素，直接与首元素对调，其余不动。

排除法：B 是完整排序；C 交换对象错；D 是降序结果。

关联 · 选择第 i 轮就位（C5）：第 1 轮后 a[0] 已就位。

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

解析：i 从 4 递减：第 1 轮最大 8 换到末位 → 5 3 7 1 8；第 2 轮 7 就位 → 5 3 1 7 8；第 3 轮 5 就位 → 1 3 5 7 8 → 升序完成。正确答案 A。

实现要点：对称写法 = i 从 n-1 递减、找 [0, i] 最大值、swap(a[i], a[p])。手算从数组末尾往前固定元素。

排除法：B 是降序；C 是第一轮后的中间状态；D 次序错。

关联 · 选最大放末尾（C6）：两种方向等价。

考点：选择的比较次数（J5）。

解析：比较次数 $= (n-1) + (n-2) + \cdots + 1 = 3 + 2 + 1 = 6$（与数据内容无关）。正确答案 A。

实现要点：选择排序比较次数固定 $n(n-1)/2$。手算：内层循环圈数递减，逐轮相加。

排除法：B（12）是 $n(n-1)$ 的误解；C（4）只算最后一轮；D 无依据。

关联 · 选择的比较与交换次数（C2）：比较 $O(n^2)$、交换 $O(n)$。

考点：每轮就位的元素（J6）。

解析：第 1~4 轮分别把 1、2、3、4 放到最前，每轮输出 a[i] → 1 2 3 4。正确答案 A。

实现要点：第 $i$ 轮结束后 a[i] 就是全局第 $i+1$ 小元素（已就位）。手算：每轮圈出未排部分的最小值。

排除法：B 是降序方向；C 多输出第 5 个元素（外层只到 n-2）；D 次序错。

关联 · 选择第 i 轮就位（C5）：就位性质的代码实证。

考点：插入排序输出结果（K1）。

解析：逐个插入：3→3 5、8 不动、1 插到最前、7 插到 5 与 8 之间 → 1 3 5 7 8。正确答案 A。

实现要点：插入框架 = key = a[i] 暂存 + while 把比 key 大的后移 + a[j+1] = key 落位。手算：像理牌，每张新牌从右往左找到位置。

排除法：B 是降序；C 只插了第一个；D 次序错。

关联 · 插入的基本思想（D1）：抓牌类比。

考点：插入两轮后的状态（K2）。

解析：插 2 → 2 9 7 4 1；插 7（9 后移）→ 2 7 9 4 1。前 3 个元素有序。正确答案 A。

实现要点：第 $i$ 轮后前缀 a[0..i] 有序。手算：只看前缀，新元素落位后其余不动。

排除法：B 把后面的元素也算进来排了；C 没把 9 后移；D 是完整结果。

关联 · 插入的前缀有序（D5）：前缀有序 ≠ 最终就位。

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

解析：{4,3,2,1} 移动 $1 + 2 + 3 = 6$ 次（第 1 个插 1 次、第 2 个插 2 次、第 3 个插 3 次）。正确答案 A。

实现要点：逆序是最坏输入，移动次数 $= n(n-1)/2$。手算：每轮 while 执行次数 = 新元素前面比它大的个数。

排除法：B（4）只算了 $n-1$；C（12）是 $n(n-1)$ 的误解；D 无依据。

关联 · 已有序的移动次数（K5）：最好 0 次、最坏 $n(n-1)/2$ 次。

考点：内层 while 条件的作用（K4）。

解析：a[j] > key 逐个把比 key 大的元素右移一位，循环停止处就是 key 的插入位置。正确答案 A。

排除法：B 与越界无关（越界靠 j >= 0 防）；C 不检测重复；D 与速度无关。

关联 · 插入的移动实现（D6）：移动 + 落位两步走。

考点：已有序的移动次数（K5）。

解析：数组已有序，内层 a[j] > key 一次都不成立 → 移动 0 次，输出 0。正确答案 A。

实现要点：最好情况 = 有序输入 → $O(n)$（只比较不移动）。对比 K3：同样 4 个元素逆序移动 6 次。

排除法：B（4）是插入次数；C（10）是全部比较次数；D 无依据。

关联 · 插入的时间复杂度（D2）：最好 $O(n)$ 的来源。

考点：插入排序前缀状态（K6）。

解析：插 1 → 1 3 4 1 5 9；插 4（前面 3 < 4 不移动）→ 不变。前 3 个 1 3 4 有序，后面未动。正确答案 A。

实现要点：注意数组里有两个 1——第一个 1 是"后来插到前面"的，说明前缀只是暂时有序（D5）。手算时先写 key、再数 while 移动次数。

排除法：B 是完整排序结果；C 是原数组；D 交换次序错。

关联 · 插入两轮后的状态（K2）：同款题的 6 元素版。

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

解析：基准 6：小于 6 的 1、2、3、5 依次换到前面，最后 6 与 a[4] 交换落位 → 5 1 2 3 6 7 9。正确答案 A。

实现要点：分区 = i 记录"最后一个小于基准的位置"，遇到小于基准的 i++ 交换；最后 swap(a[0], a[i]) 让基准落位。手算：小于基准的按顺序挤到左边，基准放中间。

排除法：B 是完整排序结果；C 没做最后的基准落位交换；D 落位位置错。

关联 · 快排的基本思想（E1）：分区是快排的核心。
大纲注：本细节属提高级大纲【5/6】，按用户教学规划保留（J 复赛必备扩展）。

考点：快排递归输出（L2）。

解析：分区 + 左右递归，完整排序 → 1 2 3 4 5 6。正确答案 A。

实现要点：快排递归框架 = if (l >= r) return + 分区 + qs(l, i-1) + qs(i+1, r)。手算：先分区看基准落位，再分别处理两段。

排除法：B 是降序；C 是原数组；D 右边没排好。

关联 · 快排缺递归边界（P4）：没有 l >= r 的终止会栈溢出。
大纲注：本细节属提高级大纲【5/6】，按用户教学规划保留（J 复赛必备扩展）。

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

解析：基准 3，小于 3 的有 1、1、2 三个 → 基准最终落在下标 3。正确答案 A。

实现要点：分区后基准落位下标 = "小于基准的元素个数"（基准从 a[0] 出发时）。手算：数出比基准小的个数即可，无需模拟交换。

排除法：B 漏数一个 1；C 多算；D 是基准起点。

关联 · 一次分区后的状态（L1）：落位下标的快捷算法。
大纲注：本细节属提高级大纲【5/6】，按用户教学规划保留（J 复赛必备扩展）。

考点：快排的递归深度（L4）。

解析：已有序 {1,2,3,4,5} + 首元素基准：每层只排除基准自身，递归链 qs(0,4) → qs(1,4) → qs(2,4) → qs(3,4)（qs(4,4) 因 l >= r 直接返回不计数）→ 最大深度 4。正确答案 A。

实现要点：最坏递归深度 = $n-1$（叶子调用不进入函数体）。手算：画递归链，注意 l >= r 的调用不增加深度。

排除法：B（5）把叶子调用也计入；C、D 是随机输入的量级。

关联 · 快排的空间开销（E4）：栈深最坏 $O(n)$。
大纲注：本细节属提高级大纲【5/6】，按用户教学规划保留（J 复赛必备扩展）。

考点：快排最坏情况识别（L5）。

解析：已有序 + 固定首元素基准 → 每次分区极不平衡（一边空、一边 $n-1$ 个）→ $O(n^2)$。✅ 正确

排除法：无（判断题）。混淆点：反过来"固定首元素 + 随机数组"平均仍 $O(n \log n)$。

关联 · 快排的最坏情况（H2）：触发条件与对策。
大纲注：本细节属提高级大纲【5/6】，按用户教学规划保留（J 复赛必备扩展）。

考点：随机基准防退化（L6）。

解析：随机选基准（或三数取中）使最坏输入几乎不会出现，期望 $O(n \log n)$。正确答案 A。

排除法：B/C 是退化的根源；D 用 $O(n^2)$ 算法替代是倒退。

关联 · 快排的时间复杂度（E2）：平均优秀的保证。
大纲注：本细节属提高级大纲【5/6】，按用户教学规划保留（J 复赛必备扩展）。

考点：每轮基准下标序列（L7）。

解析：qs(0,4) 基准 2 落位 1 → 输出 1；qs(2,4) 基准 5 落位 4 → 输出 4；qs(2,3) 基准 3 落位 2 → 输出 2。序列 1 4 2。正确答案 A。

实现要点：递归顺序 = 先序（先分区输出、再左右递归）。手算：按"基准值排序后位置"推落位，按递归展开顺序排输出。

排除法：B 把右子树输出提前；C 是首轮落位搞反；D 无依据。

关联 · 快排递归输出（L2）：输出时机决定序列形态。
大纲注：本细节属提高级大纲【5/6】，按用户教学规划保留（J 复赛必备扩展）。

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

解析：双指针 i、j 分别扫两段，谁小取谁 → 1 2 3 4 5 7 8 9。正确答案 A。

实现要点：merge 框架 = 双指针比较 + 两个"收尾"while（把剩余段倒进 tmp）+ 回写。手算：左右各放一根手指，反复取较小者。

排除法：B 是原数组；C 是降序；D 是两段原样拼接。

关联 · 归并的基本思想（E5）：合并是归并的核心。
大纲注：本细节属提高级大纲【5/6】，按用户教学规划保留（J 复赛必备扩展）。

考点：归并排序输出（M2）。

解析：递归分治 + 合并，完整排序 → 1 3 5 6 7 8。正确答案 A。

实现要点：归并框架 = ms(l, mid) + ms(mid+1, r) + merge + 回写。手算：自底向上看——先相邻两两合并，再四四合并。

排除法：B 是降序；C 是原数组；D 合并不完整。

关联 · 合并两个有序段（M1）：框架与 M1 的合并函数衔接。
大纲注：本细节属提高级大纲【5/6】，按用户教学规划保留（J 复赛必备扩展）。