GESP 八级 · GESP 202506 C++ 八级 第 12 题

下面 quick_sort 函数试图实现快速排序算法，两横线处分别应该填入的是（ ）。

void swap(int & a, int & b) {
    int temp = a; a = b; b = temp;
}

int partition(int a[], int l, int r) {
    int pivot = a[l], i = l + 1, j = r;
    while (i <= j) {
        while (i <= j && a[j] >= pivot)
            j--;
        while (i <= j && a[i] <= pivot)
            i++;
        if (i < j)
            swap(a[i], a[j]);
    }
    ________;           // 在此处填入选项
    return ________;    // 在此处填入选项
}

void quick_sort(int a[], int l, int r) {
    if (l < r) {
        int pivot = partition(a, l, r);
        quick_sort(a, l, pivot - 1);
        quick_sort(a, pivot + 1, r);
    }
}

A.

swap(a[l], a[i])
i

B.

swap(a[l], a[j])
i

C.

swap(a[l], a[i])
j

D.

swap(a[l], a[j])
j

STL 容器：vector（动态数组）、set/map（红黑树，有序）、unordered_set/map（哈希表，无序）。注意迭代器失效问题。

填空时注意语法完整性：分号、括号匹配、函数参数类型和个数、返回值类型。

【考点】快速排序｜函数指针逻辑｜边界条件

1. 考纲定位 GESP 八级排序模块必考。命题人专卡"会背不会写"的漏洞——partition 最后一步 swap 与返回值，90% 考生只记"pivot 归位"却搞不清具体位置。

2. 解题思维 核心逻辑：循环结束时 i>j，a[j] 是最后一个小于 pivot 的元素，a[l] 是 pivot。必须 swap(a[l], a[j]) 才能把 pivot 放回正确位置，此时 pivot 下标为 j，故 return j。

3. 陷阱拆解 A 项 swap(a[l], a[i]) 错在 i 已越过 j，a[i] 是第一个大于 pivot 的元素（或越界），交换后 pivot 跑到 i 处，破坏分区；B 项 swap 正确但 return i 错，pivot 实际在 j；C 项 swap 错且 return j 巧合正确，但 swap 错误导致分区失败；D 项 swap(a[l], a[j]) 且 return j 完美契合。

4. 反命题思维 若把 swap 写成 swap(a[l], a[i]) 会怎样？pivot 将位于 i 处，递归时 l 到 i 的区间包含大于 pivot 的元素，排序必错。永远记住：i 是"第一个大于 pivot 的位置"，j 是"最后一个小于 pivot 的位置"，pivot 属于 j。