Appearance
题目
使用快速排序算法对数据进行升序排序,若经过一次划分后得到的数据序列是 68, 11, 70, 23, 80, 77, 48, 81, 93, 88,则该次划分的枢轴是( )。
错因
A
把"序列里最小的元素"当成枢轴。11 确实是序列最小值,但快排的枢轴不是"最小值"——它是划分后落在最终位置上的那个元素,要满足"左边都比它小,右边都比它大"。看 11 的左边是 68(>11),不满足"左边全 ≤ 11",11 不可能是枢轴。
B
只看到 70 两侧元素分布有点像"小、大",没逐个核对。70 左边是 68, 11(都 < 70)✓,但右边是 23, 80, 77, 48, 81, 93, 88——23 < 70,违反"右边全 > 枢轴"的性质,70 不是枢轴。
C
跟 B 类似的偷懒。80 左边 68, 11, 70, 23 都 < 80 ✓,但右边 77 < 80(也 48 < 80),违反性质。80 也不是。
总解析
枢轴的判定准则:一次划分后,枢轴必须落在最终位置——即"左边所有元素 ≤ 枢轴,右边所有元素 ≥ 枢轴"(升序时)。逐个候选验证最快。
序列:68, 11, 70, 23, 80, 77, 48, 81, 93, 88(下标 0..9)
逐项验证:
| 候选 | 左边 | 右边 | 检验 |
|---|---|---|---|
| 11 (idx 1) | 左 68 > 11 ✗ | ||
| 70 (idx 2) | 右 23 < 70 ✗ | ||
| 80 (idx 4) | 右 77, 48 < 80 ✗ | ||
| 81 (idx 7) | {68, 11, 70, 23, 80, 77, 48}(max=80 ≤ 81) | {93, 88}(min=88 ≥ 81) | ✓ |
81 的左边最大是 80,右边最小是 88,恰好夹住 81——这就是它划分完成的最终位置。
最终答案是 D(81)。
实战技巧:碰到"找枢轴"题,先扫一眼两侧分界的元素——枢轴左边的最大值和右边的最小值都必须把枢轴夹在中间。从中间往两端扫往往比逐个候选快。