GESP 五级 · GESP 202509 C++ 五级 第 11 题

下述 C++ 代码实现了快速排序算法，下面说法错误的是（ ）。

int partition(vector<int>& arr, int low, int high) {
    int i = low, j = high;
    int pivot = arr[low];                    // 以首元素为基准
    while (i < j) {
        while (i < j && arr[j] >= pivot) j--;  // 从右往左查找
        while (i < j && arr[i] <= pivot) i++;  // 从左往右查找
        if (i < j) swap(arr[i], arr[j]);
    }
    swap(arr[i], arr[low]);
    return i;
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low >= high) return;
    int p = partition(arr, low, high);
    quickSort(arr, low, p - 1);
    quickSort(arr, p + 1, high);
}

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】快速排序｜分区操作（partition）｜递归复杂度分析

🎯 考纲定位

GESP 五级·算法设计与分析——排序算法。命题人专门挑这道题，就是卡住那些"背结论不验细节"的考生：知道快速排序 O(n log n) 却说不清 partition 为什么必须按这个顺序写。