题目

排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一"趟"。下列序列中，不可能是快速排序第二趟结果的是( )。

错因

A

误以为这种状态需要更多趟。其实只要第一趟取 pivot=28（28 落到位置 5），第二趟在右子区间 [60,32,72] 取末元素 72 作 pivot（72 是右子最大值，分区后到末位），就能在两趟内得到 A。学生通常没意识到第二趟可以是子区间内任意一次合法 partition。

B

误以为同时让 2 和 72 都落到首末两端需要至少 3 趟。其实第一趟取 pivot=2（恰为最小值时，其他元素都 ≥ 2 都留在右边）让 2 到位置 1；第二趟在右子区间取 pivot=72（恰为最大值时，其他都 ≤ 72 都留在左边）让 72 到位置 8。中间 6 个元素未被处理过，所以保留输入时的相对顺序。两趟到位。

C

看到 2、28、32 三个元素都已在最终排序位置，就以为需要 3 个 pivot、即 3 趟。但 pivot 数实际只有 2 个：28（第一趟）和 32（第二趟在右子区间）；位置 1 上的 2 是分区时作为 <28 的最小元素"巧好"被放到子区间最左端，不是 pivot——只是巧合性的最终位置。

总解析

核心思路：快速排序每趟把 1 个 pivot 放到其最终排序位置，其他元素相对位置依实现而定。两趟之后至少有 2 个 pivot 在最终位置，但具体哪些位置是 pivot 取决于 pivot 选取规则（一般取首/末元素）。

排序后的目标序列：

逐项验证：

选项	推导路径	是否合法
A	一趟 pivot=28 → 二趟在右子取末元素 pivot=72	✓ 可达
B	一趟 pivot=2（首=最小）→ 二趟在右子取末元素 pivot=72（最大）	✓ 可达
C	一趟 pivot=28 → 二趟在右子取首元素 pivot=32（位置 1 的 2 是巧合）	✓ 可达
D	见下	✗ 不可达

详细论证 D = [5, 2, 12, 28, 16, 32, 72, 60] 不可能：

D 中处于最终排序位置的元素是 12（位置 3） 和 32（位置 6）——两次 pivot 必然只能从这两个里选。

情形 1：第一趟 pivot=12，则分区后 [<12] | 12 | [>12] = [5,2] | 12 | [28,16,32,72,60]。第二趟必须在右子区间使 32 成为 pivot：

• 取右子首元素 28 作 pivot：得 [16] | 28 | [32,72,60]，第 4-5 位是 16,28——与 D 的 28,16 顺序相反。
• 取右子末元素 60 作 pivot：60 落到子区间排序位置 4（即整体位置 7）——与 D 中 72 在第 7 位矛盾。

→ 推不出 D。

情形 2：第一趟 pivot=32，则分区后 [5,2,12,28,16] | 32 | [72,60]。第二趟必须在左子区间使 12 成为 pivot：

• 取左子首元素 5 作 pivot：得 [2] | 5 | [12,28,16]，前两位变成 [2,5]——与 D 的 [5,2] 顺序相反。
• 取左子末元素 16 作 pivot：16 落到子区间排序位置 4（即整体位置 4）——与 D 中 28 在位置 4 矛盾。

→ 推不出 D。

两种 pivot 选择都无法在两趟内到达 D 的状态，所以 D 不可能是第二趟的结果。

最终答案是 D。