GESP 五级 · GESP 202503 C++ 五级 第 10 题

考虑以下 C++ 代码实现的快速排序算法，将数据从小到大排序，则横线上应填的最佳代码是（ ）。

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // 基准值
    int i = low - 1;

    for (int j = low; j < high; j++) {
        // 在此处填入代码
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

// 快速排序
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

A.

if (arr[j] > pivot) {
    i++;
    swap(arr[i], arr[j]);
}

B.

if (arr[j] < pivot) {
    i++;
    swap(arr[i], arr[j]);
}

C.

if (arr[j] < pivot) {
    swap(arr[i], arr[j]);
    i++;
}

D.

if (arr[j] == pivot) {
    i++;
    swap(arr[i], arr[j]);
}

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

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

【考点】快速排序｜partition划分｜数组交换

🎯 考纲定位：GESP五级C++算法模块。命题人卡住的是"快速排序partition核心逻辑"——学生背了算法但没理解划分本质，看到代码就凭感觉选。

🧠 解题思维：快速排序partition的核心是：把比基准小的放左边，比基准大的放右边。i 始终指向"左侧已放好小数的最后一个位置"，j 从左往右扫描。当 arr[j] < pivot 时，说明 j 这个位置该放小数了，所以先 i++ 腾出空位，再 swap(arr[i], arr[j]) 把小数换过去。循环结束后，i+1 正好是基准应该落的位置，swap 一下完成划分。

🪤 陷阱拆解：A 错在条件反了，把大于基准的换过去，最后基准会落到小数区；C 错在顺序，先 swap 再 i++，i 还没指向空位就交换了，会把基准左边的数换走；D 只处理相等值，大于基准的全漏了。

🔄 反命题思维：如果把 if (arr[j] < pivot) 改成 >=，基准会偏左；选第一个元素作基准，数组相等时可能退化成 O(n²)。刷到类似题先问：基准在哪？i 代表什么？换哪边？