GESP 五级 · GESP202609 C++ 五级 第 12 题

下面快速排序的划分函数以 a[right] 为枢轴，并把不大于枢轴的元素移动到左侧。横线处应填写 （　　）。

int partition(int a[], int left, int right) {
int pivot = a[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (__________________) {
i++;
swap(a[i], a[j]);
}
}
swap(a[i + 1], a[right]);
return i + 1;
}

快速排序的核心是划分操作：选定枢轴后，把不大于它的元素移到左侧，大于它的移到右侧。本题代码已经实现了两指针交换框架，横线处只需填判断条件。看到题先想：枢轴是 a[right]，循环里 j 从左往右扫描，i 是左侧已处理区域的边界。条件成立时 i 右移并交换 a[i] 与 a[j]，说明这个条件要筛选出"应该留在左侧"的元素。因此条件必须是 a[j] 与枢轴的大小比较，且方向要符合"不大于枢轴"的题意。

选项 B 把方向反了，会选出大于枢轴的元素，导致枢轴最终被放到左侧，破坏快速排序的分区性质。选项 C 误用 a[i] 而非 a[j]，i 是边界索引，此时 a[i] 还没被判定，逻辑上毫无意义。选项 D 等价于 a[j] > a[right]，与 B 实质相同，只是换了写法迷惑考生。

1. 考纲定位

本题考查《GESP 考试大纲》五级"算法与数据结构"模块中的快速排序知识点。命题人放这道题，卡住的是绝大多数考生对划分算法（partition） 的机械记忆——他们背过"快速排序用枢轴"，但没真正理解划分过程中枢轴与元素比较的方向。五级要求"能分析排序算法的划分过程"，这道题就是考查这个理解深度。

2. 解题思维

完整思考链：

1. 看枢轴定义：int pivot = a[right]; 枢轴是右端点元素。 2. 看循环结构：j 从左到右扫描，i 初始为 left-1，每次条件成立就 i++ 并交换 a[i] 与 a[j]。 3. 看最终操作：swap(a[i+1], a[right]); 把枢轴放到 i+1 位置。 4. 推导条件含义：循环结束后，a[left..i] 都是"满足条件"的元素，a[i+1..right-1] 是"不满足条件"的元素。枢轴被放到 i+1，说明枢轴右侧全是大于它的元素——因此条件筛选的是不大于枢轴的元素。 5. 填条件：a[j] <= pivot。

数值推演（以数组 [3, 1, 4, 2, 5]，枢轴 5 为例）：

• j=0：a[0]=3 <= 5，条件成立，i=0，交换 a[0] 与 a[0]（不变）。
• j=1：a[1]=1 <= 5，条件成立，i=1，交换 a[1] 与 a[1]（不变）。
• j=2：a[2]=4 <= 5，条件成立，i=2，交换 a[2] 与 a[2]（不变）。
• j=3：a[3]=2 <= 5，条件成立，i=3，交换 a[3] 与 a[3]（不变）。
• 循环结束，i=3，swap(a[4], a[4])，枢轴仍在原位。

若填 a[j] > pivot，则 3,1,4,2 都不满足，i 保持 left-1，枢轴被换到最左侧，整个分区逻辑彻底错误。

这一类题的通法：遇到快速排序划分函数填空，先锁定枢轴定义，再看循环中 i 与 j 的交换逻辑，最后根据"枢轴最终位置"反推条件方向。记住：枢轴右侧全是大于它的元素，所以条件一定是"不大于枢轴"。