第 19 章 快排与归并 · 知识细节练习

考点：分治三步骤（A1）。

解析：分治三步骤 = 分解（Divide）→ 解决（Conquer）→ 合并（Combine）：把大问题分解为规模更小的同构子问题，递归解决子问题，最后把子问题的解合并成原问题的解。✅ 正确

排除法：无（判断题）。混淆点：合并步骤不是"可选"的——归并排序的合并是核心，快排的"合并"是隐式的（分区后基准落位、左右已分离，无需显式合并）。

关联 · 快排与归并都是分治（A2）：快排分解=分区、合并=无（自动完成）；归并分解=对半切、合并=merge 函数。

考点：快排与归并都是分治（A2）。

解析：快排的"解决"（分区 partition）在递归之前做——先分区把基准落位，再递归排左右；归并的"合并"在递归之后做——先递归排两半，再 merge。这是两者分治结构的本质差异。✅ 正确

排除法：无（判断题）。混淆点：快排没有显式合并步骤，但它的分区本身就是"合并"的替代——保证左段都 $\le$ 右段。

关联 · 分区操作（B2）：分区是快排的核心。

考点：递归出口（A3）。

解析：分治递归出口 = 子问题规模足够小、直接返回。快排与归并的出口都是区间长度 $< 2$（即 $l \ge r$）——单个元素（或空区间）天然有序、无需再分。✅ 正确

排除法：无（判断题）。混淆点：出口写成 $l > r$ 会漏掉单元素区间（多一次无意义递归但不影响结果）；漏掉出口则死递归（P5）。

关联 · 递归无出口（P5）：没有出口 → 栈溢出。

考点：分治与减治的区别（A4）。

解析：分治：分解成多个子问题、全部解决后合并（归并、快排、最大子段和）；减治：每轮只保留一个子问题继续求解（二分查找每次只搜一半、快速幂每次指数减半）。✅ 正确

排除法：无（判断题）。混淆点：减治不合并——二分查找"丢弃"另一半而不是合并两半结果。

关联 · 二分查找是减治（G1）：查找类问题常用减治，排序类常用分治。

考点：分治的复杂度直觉（A5）。

解析：每层两个 $n/2$ 子问题 + $O(n)$ 合并：第 1 层 $n$、第 2 层 $2 \times n/2 = n$、…、第 $k$ 层 $2^k \times n/2^k = n$——每层合计都是 $O(n)$，共 $\log_2 n$ 层，总 $O(n \log n)$。✅ 正确

排除法：无（判断题）。混淆点：这是"每层求和"的分析法——归并排序、快排平均、堆排序都由此得出 $n \log n$。

关联 · 层数与每层代价（D7）：归并就是教科书式的"每层 $O(n)$"。

考点：分治的适用条件（A6）。

解析：分治适用于子问题独立、同构的场景。若子问题大量重叠（朴素斐波那契：$f(n)$ 展开出 $f(n-2)$ 两遍、$f(n-3)$ 三遍…），重复计算量爆炸为指数级——需要记忆化/递推而非纯分治。✅ 正确

排除法：无（判断题）。混淆点：重叠子问题不是分治的锅，是"无缓存递归"的锅；DP 正是"分治 + 缓存"。

关联 · 分治与递推（G5）：递推自下而上天然复用子问题结果。

考点：基准元素（B1）。

解析：基准（pivot）可从首/尾/中间/随机取——选择方式不影响正确性，但影响最坏情况触发概率：固定取首元素 + 已序输入 → 必触发 $O(n^2)$；随机/三数取中 → 期望 $O(n \log n)$。✅ 正确

排除法：无（判断题）。混淆点："基准必须是中间元素"——错，任何位置的元素都能当基准。

关联 · 基准优化（C5）：随机基准与三数取中是工程标配。

考点：分区操作（B2）。

解析：分区（partition）目标：把基准放中间，左侧都 $\le$ 基准、右侧都 $\ge$ 基准——注意分区后数组并未整体有序，只是"基准对"（左小右大）。✅ 正确

排除法：无（判断题）。混淆点：一次分区 ≠ 排序完成，后续还要递归左右两段。

关联 · 基准落位（B3）：分区后基准位置就是最终位置。

考点：基准落位（B3）。

解析：分区后基准左小右大，该位置就是基准在最终有序数组中的位置——递归时把它排除在外（处理 $[l, p-1]$ 与 $[p+1, r]$）。✅ 正确

排除法：无（判断题）。混淆点：基准不参与后续递归——若把基准也纳入递归（P2 的 $[l, r]$ 不缩小），死递归。

关联 · 递归子区间（B4）：落位是"排除基准"的依据。

考点：递归子区间（B4）。

解析：分区后基准在 $p$，递归处理 $[l, p-1]$ 与 $[p+1, r]$——基准已落位，排除。✅ 正确

排除法：无（判断题）。混淆点：Hoare 分区写法里分界点是 $j$（左段 $[l, j]$、右段 $[i, r]$，$i > j$），基准可能还在其中一段里，但两段已互不越界。

关联 · 分区返回值含义（J6）：$i, j$ 相遇错开，两段分离。

考点：不稳定的原因（B5）。

解析：快排不稳定：分区交换可能把相等的元素跨过彼此（如基准与远处相同值交换），相等元素的原始相对顺序被打乱。✅ 正确

排除法：无（判断题）。混淆点：稳定性只关乎"相等元素"，与大小关系无关；选择/堆排序同样不稳定，归并/插入/冒泡稳定。

关联 · 稳定性对比（F1）：稳定性总表要背熟。

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

解析：快排平均 $O(n \log n)$——期望每层分区比较 $O(n)$、期望层数 $O(\log n)$。✅ 正确

排除法：无（判断题）。混淆点：平均 ≠ 最坏；最坏 $O(n^2)$ 是已序+固定基准的退化场景。

关联 · 平均复杂度来源（C6）：期望分析见 C 组。

考点：原地排序（B7）。

解析：快排是原地排序：分区只做元素交换，除递归栈外不需要 $O(n)$ 辅助数组（对比归并需要）。✅ 正确

排除法：无（判断题）。混淆点："原地"指额外空间 $O(1)$ 或 $O(\log n)$ 级别；快排递归栈占 $O(\log n)$，仍算原地。

关联 · 空间对比（F2）：快排空间优势是其工程主流的原因之一。

考点：最坏情况的触发（C1）。

解析：已序（或逆序）+ 固定取首元素 → 每轮分区基准落在端点，只排好 1 个元素，剩余 $n-1$ 继续 → 共 $n$ 层、每层 $O(n)$ → $O(n^2)$。✅ 正确

排除法：无（判断题）。混淆点：全部相等输入对本实现不退化（每轮基准与自身交换后均分？——其实对 Hoare 分区，全相等时每次分区接近均分，复杂度 $O(n \log n)$）。

关联 · 最坏递归深度（C2）：退化时深度 $n$。

考点：最坏递归深度（C2）。

解析：最坏（每层只排好 1 个）时递归深度 $= n$ 层——这正是栈溢出风险点（$n = 10^6$ 时深度 100 万层必爆栈）。✅ 正确

排除法：无（判断题）。混淆点：最好情况深度 $\log_2 n$；随机基准期望深度 $O(\log n)$。

关联 · 空间复杂度（C4）：栈深度即空间。

考点：最好情况（C3）。

解析：最好情况 = 每轮分区接近均分（基准落在中位附近）→ 深度 $\log_2 n$、每层 $O(n)$ → $O(n \log n)$。✅ 正确

排除法：无（判断题）。混淆点：已序数组不是最好情况（对固定首基准反而是最坏！）。

关联 · 最好情况（C3 与 B6）：平均行为接近最好。

考点：空间复杂度（C4）。

解析：快排额外空间 = 递归栈：平均/最好 $O(\log n)$，最坏 $O(n)$（退化时深度 $n$）。不计原数组本身。✅ 正确

排除法：无（判断题）。混淆点：不是 $O(1)$——递归栈也算空间；也不是 $O(n \log n)$。

关联 · 空间对比（F2）：对比归并 $O(n)$ 辅助数组。

考点：基准优化（C5）。

解析：随机选基准与三数取中（首/中/尾取中位数）都能避免"已序输入必退化"——随机化后已序输入只是普通输入，期望 $O(n \log n)$。✅ 正确

排除法：无（判断题）。混淆点：优化不改变最坏上界（理论上仍可 $O(n^2)$），但消灭了"自然输入触发最坏"的确定性。

关联 · 三数取中（O7）：三数取中的实现细节。

考点：平均复杂度来源（C6）。

解析：平均分析的 $\log n$ 来自期望递归层数：随机基准下每层期望均分程度足够好，总比较期望 $O(n \log n)$。✅ 正确

排除法：无（判断题）。混淆点：期望分析 ≠ 均摊分析；快排的平均是"对随机输入的期望"。

关联 · 复杂度求和直觉（C7）：每层 $O(n)$ × 期望层数。

考点：复杂度求和直觉（C7）。

解析：每层分区合计 $O(n)$，期望 $\log_2 n$ 层 → 总 $O(n \log n)$。✅ 正确

排除法：无（判断题）。混淆点：$O(n)$ 是层内合计——每层所有分区加起来只扫一遍数组。

关联 · 分治的复杂度直觉（A5）：同一分析框架。

考点：二分序列（D1）。

解析：归并第一步 = 从中间一分为二，递归排序左右两半（分解），最后合并。✅ 正确

排除法：无（判断题）。混淆点：归并没有"选基准"——分解是位置对半，与值无关。

关联 · 快排与归并都是分治（A2）：分解方式对比。

考点：递归到单个元素（D2）。

解析：区间长度 $1$ 时单个元素天然有序，直接返回（递归出口）——归并的"解决"在出口处是平凡的。✅ 正确

排除法：无（判断题）。混淆点：出口是 $l \ge r$；长度 0 的区间（$l > r$）同样返回。

关联 · 递归出口（A3）：分治出口的统一写法。

考点：合并两个有序序列（D3）。

解析：双指针合并 $\{1,3,5\}$ 与 $\{2,4,6\}$：$1<2$ 取 1；$3>2$ 取 2；$3<4$ 取 3 → 前三个 1, 2, 3。✅ 正确

排除法：无（判断题）。混淆点：合并是"每次取两头较小者"，不是交错取。

关联 · 合并过程输出（K1）：代码版同题。

考点：辅助数组（D4）。

解析：合并需要 $O(n)$ 临时数组暂存合并结果再拷回——这是归并空间 $O(n)$ 的来源。✅ 正确

排除法：无（判断题）。混淆点：辅助数组是"每层复用同一个"，总空间 $O(n)$ 而非 $O(n \log n)$。

关联 · 空间对比（F2）：快排原地 vs 归并 $O(n)$。

考点：稳定性（D5）。

解析：合并时左右相等先取左边（a[i] <= a[j] 走左分支）——相等的两个元素，左边的保持在前，相对顺序不变 → 稳定。✅ 正确

排除法：无（判断题）。混淆点：等号写反（P4）立即不稳定；等号归属是稳定性判定的第一细节。

关联 · 稳定性等号反（P4）：错误示范。

考点：复杂度始终稳定（D6）。

解析：归并对半分解、每层合并 $O(n)$——与输入分布无关，最好=最坏=平均 $O(n \log n)$。✅ 正确

排除法：无（判断题）。混淆点：这是归并对比快排的核心优势：无最坏退化。

关联 · 最坏情况对比（F3）：快排最坏 $O(n^2)$ vs 归并 $O(n \log n)$。

考点：层数与每层代价（D7）。

解析：对半分解 $\log_2 n$ 层；每层所有合并合计扫 $O(n)$ 个元素 → 总 $O(n \log n)$。✅ 正确

排除法：无（判断题）。混淆点：每层合计 $O(n)$ 而非每层 $O(n \log n)$。

关联 · 分治的复杂度直觉（A5）：标准"每层求和"。

考点：逆序对定义（E1）。

解析：逆序对 = $i < j$ 且 $a_i > a_j$ 的数对——前面的数比后面的大。✅ 正确

排除法：无（判断题）。混淆点：升序序列逆序对 = 0；降序 = $n(n-1)/2$。

关联 · 逆序对与冒泡交换次数（E3）：冒泡每交换一次消掉一个逆序对。

考点：归并计数逆序对（E2）。

解析：合并时若右半边元素 $a_j$ 先被取走，说明 $a_j$ 小于左半边当前所有剩余元素（它们都在 $a_j$ 前面）→ 逆序对 += 左剩余个数（$m - i + 1$）。✅ 正确

排除法：无（判断题）。混淆点：不是加 1——一次取右可能带来多个逆序对。

关联 · 逆序对计数填空（L3/O5）：cnt += m - i + 1 是标准句。

考点：逆序对与冒泡交换次数（E3）。

解析：冒泡每次交换相邻元素恰好消掉一个逆序对；排序完成 = 逆序对清零 → 交换次数 = 逆序对总数。✅ 正确

排除法：无（判断题）。混淆点：这是"相邻交换"性质；快排的交换不是相邻交换，无此等式。

关联 · 逆序对定义（E1）：升序 0 个 → 冒泡 0 次交换。

考点：归并的其他应用（E4）。

解析：归并思想三应用：求逆序对（合并时计数）、链表排序（无下标、用指针归并）、外部排序（内存装不下时多路归并磁盘块）。✅ 正确

排除法：无（判断题）。混淆点：最大公约数/素数/最短路与归并无直接关系。

关联 · 归并链表（L4）：链表版归并代码。

考点：归并与快排的选择（E5）。

解析：要求稳定 → 归并（稳定）；快排不稳定，相等元素相对顺序可能被交换打乱。✅ 正确

排除法：无（判断题）。混淆点：多关键字排序、结构体按主键排且希望副键保序时，稳定性是硬需求。

关联 · 稳定性的应用场景（E6）：为什么需要稳定。

考点：稳定性的应用场景（E6）。

解析：稳定排序保证：先按次关键字排、再按主关键字稳定排 → 主关键字相同的记录保持次关键字有序——多级排序的标准套路（如先按成绩排再按学号排，同分者学号有序）。✅ 正确

排除法：无（判断题）。混淆点：不稳定的排序会把第二级顺序打乱，必须先主后次且用稳定排序。

关联 · 稳定性对比（F1）：总表。

考点：稳定性对比（F1）。

解析：归并稳定、快排不稳定。✅ 正确

排除法：无（判断题）。混淆点：稳不稳定与"快不快"无关——堆排序 $O(n \log n)$ 也不稳定。

关联 · 常见误区（F6）：稳定/原地的常见记反。

考点：空间对比（F2）。

解析：快排原地（栈 $O(\log n)$）；归并需要 $O(n)$ 辅助数组。✅ 正确

排除法：无（判断题）。混淆点：空间是归并的软肋，是快排工程首选的原因之一。

关联 · 空间对比（M5）：代码视角验证。

考点：最坏情况对比（F3）。

解析：快排最坏 $O(n^2)$（已序+固定基准）；归并最坏也是 $O(n \log n)$——无退化。✅ 正确

排除法：无（判断题）。混淆点：时间复杂度与稳定性是独立维度，别串。

关联 · 复杂度总表（F5）：全维度总表。

考点：场景选择（F4）。

解析：内存充足 + 要求稳定 + 大数据 → 归并排序（$O(n \log n)$ 且稳定；$O(n)$ 辅助空间可接受）。✅ 正确

排除法：无（判断题）。混淆点：内存紧张时快排（原地）；数据值域小用桶/计数。

关联 · 归并与快排的选择（E5）：稳定性是第一筛选条件。

考点：复杂度总表（F5）。

解析：快排：平均 $O(n \log n)$ / 最坏 $O(n^2)$ / 空间 $O(\log n)$ / 不稳定；归并：平均=最坏 $O(n \log n)$ / 空间 $O(n)$ / 稳定。✅ 正确

排除法：无（判断题）。混淆点：四维度（时间平均/时间最坏/空间/稳定性）逐项背熟，S 组单选高频。

关联 · 稳定性总表（J 组 13 章 F5）：与 J 组基础排序衔接。

考点：常见误区（F6）。

解析：快排原地但不稳定、归并稳定但不原地（需 $O(n)$ 辅助数组）——两者在稳定性与空间两个维度上恰好互补。✅ 正确

排除法：无（判断题）。混淆点："快排稳定""归并原地"是两大高频误记——稳不稳定看相等元素相对顺序，原地与否看额外数组。

关联 · 稳定性对比（F1）/ 空间对比（F2）：两个维度的互补性。

考点：二分查找是减治（G1）。

解析：二分查找每轮丢弃一半只保留一个子区间继续搜——只解决一个子问题、无合并 → 减治（divide and conquer 的变体）。✅ 正确

排除法：无（判断题）。混淆点：归并要合并两半结果，二分不合并——分治/减治的分水岭是"是否需要合并"。

关联 · 分治与减治的区别（A4）：定义对照。

考点：快速幂（G2）。

解析：$a^n$：$n$ 偶 → $a^n = (a^{n/2})^2$；$n$ 奇 → 提出一个 $a$ 再平方——每次指数减半，$O(\log n)$ 次乘法，对比朴素连乘 $O(n)$。✅ 正确

排除法：无（判断题）。混淆点：二进制视角等价——按 $n$ 的二进制位自低向高乘入对应权值。

关联 · 快速幂输出（N2）/ 快速幂填空（O6）：代码版。

考点：分治最大子段和（G3）。

解析：跨中点的最大子段 = 从中点向左的最大后缀和 + 从中点向右的最大前缀和（两段都必经中点）；与纯左、纯右三取最大。✅ 正确

排除法：无（判断题）。混淆点：漏跨中点情形 = 经典错误（答案可能偏小）；跨中点必须"左后缀+右前缀"而不是"左最大+右最大"。

关联 · 分治最大子段和代码（N3）：$O(n \log n)$ 分治版。

考点：汉诺塔（G4）。

解析：$T(n) = 2T(n-1) + 1$（移 $n-1$ 盘两次 + 最大盘一次）→ 展开 $T(n) = 2^n - 1$。✅ 正确

排除法：无（判断题）。混淆点：$2^n - 1$ 是指数增长——汉诺塔是分治的"反面教材"（子问题两个、规模只减 1）。

关联 · 汉诺塔输出（N4）：移动序列的递归打印。

考点：分治与递推（G5）。

解析：分治自上而下（递归分解再回溯合并）；递推自下而上（小规模推大规模）——方向相反但可互相转化（归并递归版 ↔ 自底向上迭代版）。✅ 正确

排除法：无（判断题）。混淆点：递归树展开后的计算顺序就是递推顺序。

关联 · 自底向上迭代版（K6/L5）：递推化归并。

考点：更多分治实例（G6）。

解析：平面最近点对：按 x 排序二分，跨中线只需检查带内 $O(\delta)$ 宽度内的候选点——典型分治（分解+解决+跨区合并）。✅ 正确

排除法：无（判断题）。混淆点：求平方/判奇偶/交换变量是 $O(1)$ 基本操作，不需要分治。

关联 · 分治的适用条件（A6）：几何分治实例。

考点：分区边界（H1）。

解析：while (i <= j) 保证 i、j 相遇错开后相遇点元素也被处理；写成 i < j 时相遇位置漏判，分区可能错误（P1 实测输出 1 3 2，左段含大于基准的元素）。✅ 正确

排除法：无（判断题）。混淆点：i <= j 与内层 if (i <= j) 配对是相向扫描分区的标准写法。

关联 · 分区边界错（P1）：错误示范代码。

考点：最坏情况误判（H2）。

解析：已升序 + 固定首基准：每轮基准最小、落最左，右段只剩 $n-1$ 继续 → 共 $n$ 层 → $O(n^2)$。✅ 正确

排除法：无（判断题）。混淆点：直觉上"已序最好排"恰恰是快排的最坏——这是 S 组最爱的判断题陷阱。

关联 · 最坏情况的触发（C1）：同一个坑的概念题。

考点：合并越界（H3）。

解析：合并必须三循环完整：主循环（两段都剩）+ 左剩余搬移 + 右剩余搬移；漏掉任何一段剩余 → 结果缺元素/脏数据（P3 实测 1 3 0 0）。✅ 正确

排除法：无（判断题）。混淆点：先判断"哪段先耗尽"再搬另一段——两个 while 缺一不可。

关联 · 归并漏剩余段（P3）：错误示范代码。

考点：稳定性判定综合（H4）。

解析：相等时先取左（<=）是归并稳定的根基；等号写反（<，相等取右）→ 相等元素被"后出现的先放"→ 不稳定（P4 实测 1d 1b 顺序反转）。✅ 正确

排除法：无（判断题）。混淆点：等号归属这一个字符决定稳定性——代码审查必看。

关联 · 稳定性等号反（P4）：错误示范代码。

考点：复杂度综合判断（H5）。

解析：三结论全对：① 快排最坏 $O(n^2)$ 平均 $O(n \log n)$；② 归并最坏 $O(n \log n)$ 需 $O(n)$ 辅助空间；③ 基于比较的排序最坏下界 $\Omega(n \log n)$（决策树深度 $\ge \log_2(n!)$）。✅ 正确

排除法：无（判断题）。混淆点：下界说的是最坏情况——桶/计数等非比较排序可突破到 $O(n)$，但它们不基于比较。

关联 · 复杂度总表（F5）：本章复杂度结论的收官。

考点：分区过程输出（I1）。

解析：$x=5$：右扫 $a[4]=2$ 不大于 5、左扫 $a[0]=5$ 不小于 5 → 交换 → $\{2,3,8,1,5\}$；左扫到 $a[2]=8$、右扫到 $a[3]=1$ → 交换 → $\{2,3,1,8,5\}$；i、j 错开结束。输出 2 3 1 8 5。正确答案 A。

实现要点：相向扫描三件套——while (a[i] < x) i++ 找左大、while (a[j] > x) j-- 找右小、if (i <= j) 才交换并各自推进。手算：画出 i、j 每轮停下的位置再交换。

排除法：B 是最终有序结果（一次分区做不到）；C 是原数组；D 是错误交换序列。

关联 · 分区操作（B2）：概念题代码化。

考点：基准落位（I2）。

解析：分区结束 i=3、j=2：左段 $[0,2]=\{2,3,1\}$ 全 $\le 5$，右段 $[3,4]=\{8,5\}$ 全 $\ge 5$；基准 5 位于右段边界、下标 4，已落位（左侧都不大于它，后续递归不再移动它）。输出 4。正确答案 A。

实现要点：Hoare 分区结束后分界是「i 与 j 错开」——左段 $[l, j]$、右段 $[i, r]$；基准不保证居中，但保证左右两段值域分离。手算：写出 i、j 每轮停下的位置。

排除法：B 是初始位置；C 是中间；D 无依据。

关联 · 分区返回值含义（J6）：i、j 错开与两段分离。

考点：递归调用顺序（I3）。

解析：$\{3,1,2\}$，$x=3$：交换 $a[0]$ 与 $a[2]$ → $\{2,1,3\}$，i=1、j=1；i 再进到 2，结束。此时 $j=1$、$i=2$ → 第一次递归实参 $(0, 1)$。输出 qsort(0, 1)。正确答案 A。

实现要点：分区后先递归左段 qsort(l, j)、再递归右段 qsort(i, r)——j 是左段右端点、i 是右段左端点，两者错开 $i = j+1$。手算：分区结束时记下 i、j 值。

排除法：B 是入口参数；C/D 无依据。

关联 · 快排递归填空（O2）：左段实参的填空版。

考点：完整快排输出（I4）。

解析：递归执行完整快排后数组整体有序 → 1 2 3 4 5。正确答案 A。

实现要点：完整快排 = 分区 + 递归左段 + 递归右段，递归出口 $l \ge r$；无论中间过程如何，算法保证最终有序。手算技巧：不必模拟每一步，验证出口与两段递归即可。

排除法：B 是降序；C 是首次分区后状态；D 是部分有序。

关联 · 递归子区间（B4）：排除基准的两段递归。

考点：交换次数（I5）。

解析：$\{3,1,2\}$：第一层交换 $a[0]$ 与 $a[2]$（1 次）；左段 $\{2,1\}$ 分区交换一次（1 次）→ 共 2 次。正确答案 A。

实现要点：统计 swap 的执行次数——每轮 if (i <= j) 成立才交换；出口处长度为 0/1 的区间不产生交换。手算：递归树每个节点记录一次分区交换数。

排除法：B 漏了左段那次；C 把出口也算上；D 无依据。

关联 · 完整快排输出（I4）：同算法加计数器。

考点：分区后状态（I6）。

解析：$\{5,1,4,2,3\}$，$x=5$：交换 $a[0]$ 与 $a[4]$ → $\{3,1,4,2,5\}$，i=1、j=3；左扫 1、4、2 都 $\le 5$ 直到 i=4；右扫 $a[3]=2$ 不大于 5 停；$i \le j$？$4 \le 3$ 否 → 结束。i=4、j=3。输出 4 3。正确答案 A。

实现要点：分区结束的 i、j 是错开的（$i = j+1$ 或更远）——这是外层循环条件 i <= j 的直接后果。手算：跟踪指针每轮位置。

排除法：B 顺序反；C/D 无依据。

关联 · 分区返回值含义（J6）：分界点语义。

考点：随机基准（J1）。

解析：随机基准只是改变"选谁当基准"，不改变排序正确性——任何基准最终都得到有序数组 1 2 3 4 5；且已序输入不再必然触发 $O(n^2)$（期望 $O(n \log n)$）。✅ 正确

实现要点：随机基准套路 = rand() % (r - l + 1) 取区间内随机下标 → 换到 a[l] → 复用固定首基准的分区代码。手算：srand(1) 下结果与平台相关，但正确性恒成立。

排除法：无（判断题）。混淆点：随机化消灭"确定的最坏"，最坏上界仍是 $O(n^2)$。

关联 · 基准优化（C5）：随机化与三数取中。

考点：三数取中（J2）。

解析：首 $9$、中 $a[2]=1$、尾 $3$ 三个数的中位数：$9+1+3-9-1=3$。输出 3。正确答案 A。

实现要点：三数取中 = 首/中/尾取中位数作基准——sum - max - min 是三个数的中位数公式。手算：排序 $\{1,3,9\}$ 取中间 3。

排除法：B 是最大；C 是最小；D 是 $a[1]$。

关联 · 三数取中填空（O7）：排序法的三数取中。

考点：迭代版快排（J3）。

解析：栈模拟递归：先压右段再压左段 → 弹栈先处理左段（与递归先左后右一致）→ 最终 1 2 3。正确答案 A。

实现要点：递归转迭代 = 用栈存 (l, r)；后压先弹——想先处理左段就先压右段。手算：画出栈内容变化。

排除法：B 是降序；C/D 无依据。

关联 · 分治与递推（G5）：递归的迭代化。

考点：挖坑法分区（J4）。

解析：$x=4$ 挖坑 0；右找小 $a[3]=2<4$ → $a[0]=2$、坑变 3；左找大：1、3 都不大于 4，i 走到 3 与 j 相遇 → 循环退出 → 基准回填 $a[3]=4$ → $\{2,1,3,4\}$。输出 2 1 3 4。正确答案 A。

实现要点：挖坑法 = 基准先取出留坑 → 右找小填左坑、左找大填右坑交替 → 相遇处基准回填。手算：记录"坑"的位置流转。

排除法：B 是全排序结果；C/D 无依据。

关联 · 分区操作（B2）：同一目标的不同写法。

考点：单向扫描分区（J5）。

解析：基准 5：$j$ 扫描前 4 个元素，凡 $<5$ 就与 $a[i]$ 交换、i 前进——4、2、1、3 全部 $<5$ → i 前进到 4；最后基准与 $a[4]$ 交换（原地）→ 输出 i=4。正确答案 A。

实现要点：Lomuto 单向分区 = i 标记「小元素前缀末尾」，j 扫一遍把小数换到前缀，最后基准归位 $a[i]$。手算：i 只在遇到小于基准时前进。

排除法：B/C/D 无依据。

关联 · 挖坑法分区（J4）：分区写法全家桶。

考点：分区返回值含义（J6）。

解析：$\{2,1,3,0\}$，$x=2$：交换 $a[0]$ 与 $a[3]$ → $\{0,1,3,2\}$，i=1、j=2；左扫 $a[1]=1<2$ → i=2；右扫 $a[2]=3>2$ → j=1；结束。j=1。左段 $[0,1]=\{0,1\}$ 全 $\le 2$、右段 $[2,3]=\{3,2\}$ 全 $\ge 2$。输出 1，两段已分离。正确答案 A。

实现要点：Hoare 分区返回 $j$（或 $i$）作为分界——$[l, j]$ 与 $[i, r]$ 值域分离是后续 qsort(l, j); qsort(i, r) 的依据。手算：结束时记录 i、j 并检查两段。

排除法：B/C/D 无依据。

关联 · 分区后状态（I6）：分界语义。

考点：合并过程输出（K1）。

解析：双指针合并：$1<2$ 取 1、$3>2$ 取 2、$3<4$ 取 3 → 前三个 1 2 3。正确答案 A。

实现要点：合并 = 两个指针各指一段开头，每次取较小者、对应指针前进；一段取尽后整段搬移剩余。手算：写两行有序序列，指针一步步前进。

排除法：B 是左段全部；C 是右段；D 是倒序。

关联 · 合并两个有序序列（D3）：概念题代码化。

考点：完整归并输出（K2）。

解析：$\{3,1,4,2\}$：两半各自有序后合并 → 最终 1 2 3 4。正确答案 A。

实现要点：完整归并 = 递归两半 + 合并；正确性不依赖输入顺序。手算技巧：验证出口、中点、合并三处即可，不必全模拟。

排除法：B 是降序；C 是原数组；D 是部分有序。

关联 · 归并递归填空（O4）：填空版。