题目

下列选项中，不可能是快速排序第 2 趟排序结果的是（）。

错因

A

序列 2, 3, 5, 4, 6, 7, 9 中，2、3、6、7、9 都已经在最终位置——很容易被合理化为"两趟做完了，剩下 5、4 是某个未递归完成的子区间"。 具体地：第 1 趟选 6 为枢轴 → 6 落到正确位置 4，左右两半都未排（左半 [2,3,5,4]，右半 [7,9]）；第 2 趟左半选 2 为枢轴 → 2 落到位置 0，再选 3 → 3 到位置 1（其实已经是这样了）；右半选 7 → 7 到位置 5。结果完全合理。

B

序列 2, 7, 5, 6, 4, 3, 9 中，2 和 9 在最终位置。第 1 趟选 2 为枢轴：2 落到位置 0，左半空、右半 [7,5,6,4,3,9] 未排；第 2 趟在右半选 9 为枢轴 → 9 落到位置 6（已经在了），右半再划分但还没完成 → 中间 [7,5,6,4,3] 是部分调整状态。完全合法。

D

序列 4, 2, 3, 5, 7, 6, 9 中，5 和 9 在最终位置。第 1 趟选 5 为枢轴：5 落到位置 3，左半 [4,2,3]、右半 [7,6,9] 未排；第 2 趟左半选某枢轴（例如左划分还没动），右半选 9 → 9 已就位。完全合法。

总解析

快速排序的关键不变量：

每完成一趟划分（partition），至少有 1 个元素（枢轴）落到它最终的位置上——枢轴选定后，整个划分会把比它小的全放左边、大的全放右边，划分结束时枢轴就处于最终位置。

第 k 趟结束后，至少有 k 个元素到达最终位置（每一趟产生 ≥ 1 个枢轴，但若某子区间长度 ≤ 1 则该轮不再产生枢轴；不过原题第 2 趟时一般至少有 2 个元素已就位——除非某些特殊情况）。

更可靠的判别方法：每个候选序列都对应"某种第 1 趟枢轴 + 某种第 2 趟枢轴"组合，能否合理构造。

最终有序：2, 3, 4, 5, 6, 7, 9（位置 0..6）。

逐选项检查"已在最终位置的元素"：

选项	序列	在最终位置的元素
A	2,3,5,4,6,7,9	2(0), 3(1), 6(4), 7(5), 9(6)
B	2,7,5,6,4,3,9	2(0), 9(6)
C	3,2,5,4,7,6,9	9(6) ← 只有这一个
D	4,2,3,5,7,6,9	5(3), 9(6)

A：2、3 连续在位 → 第 1 趟选 6 为枢轴（6 到位置 4）；左半 [2,3,5,4] 第 2 趟选 2、3 → 都到位（如果左半第 2 趟是先选 2 再递归选 3）；右半 [7,9] 选 7 → 到位置 5。合理。

B：2、9 在位 → 第 1 趟选 2 为枢轴（2 到位置 0）；右半 [3,5,6,4,7,9] 第 2 趟选 9 为枢轴 → 9 到位置 6。中间序列 7,5,6,4,3 是右半划分进行中的状态。合理。

D：5、9 在位 → 第 1 趟选 5（5 到位置 3）；右半 [7,6,9] 第 2 趟选 9 → 9 到位置 6（已在）；右半剩下 7、6 还未排。左半 [4,2,3] 还未划分。合理。

C：3, 2, 5, 4, 7, 6, 9 —— 只有 9 在最终位置！而且 3↔2、5↔4、7↔6 三处都是相邻逆序对。

试图构造：

• 第 1 趟枢轴 = 9？9 在原数组末尾就有可能是初始位置（不算划分的功劳）；即使把 9 视为第 1 趟枢轴，剩下 [3,2,5,4,7,6] 经过一趟划分必然要再产生 1 个枢轴落位。但 C 中没有第二个元素在最终位置。✗
• 第 1 趟枢轴 = 别的？任何元素 x 作为第 1 趟枢轴都会在 C 序列中位于"最终位置"，可 C 里只有 9 在位 → 第 1 趟必选 9 → 矛盾如上。✗
• 退一步：是否第 1 趟与第 2 趟都不产生新最终位置？不可能——快排每一趟划分（partition）必然恰好让被选中的枢轴归位。两趟应至少产生 2 个就位元素（且均不能仅依赖"原数组末尾恰好是最大值"这种巧合）。

C 无法用快速排序的两次划分自洽地构造。

更直观的反例视角：观察 C 中 3、2 和 5、4 这种"小值在大值右边的相邻逆序对"——这意味着它们之间从未发生过基于枢轴的划分（划分会把小的拨到枢轴左、大的拨到枢轴右）。但快排两趟应该已经把序列前半段大致划分好，不该出现 3、2 和 5、4 同时反序未理的情况。

最终答案是 C（3, 2, 5, 4, 7, 6, 9）。