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

下述 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²)，要看内层是否每次都在缩小。

【考点】快速排序｜最坏情况时间复杂度｜基准选择

这段代码用首元素当基准 pivot = arr[low]，已排序时首元素是最小值，导致每次 partition 后左区间为空、右区间为 n-1 个元素。递归深度就变成 O(n)，每层 partition 扫描 O(n)，总时间 O(n)×O(n)=O(n²)。

A 项 O(n) 是把最好情况（pivot 每次平分）当成通用结论；B 项 O(log n) 容易混淆递归深度与总复杂度；D 项 O(n log n) 是平均情况，命题人特意用首元素作基准，就是为了构造最坏场景。

反命题：若把基准改成 arr[(low+high)/2]，已排序时最坏情况仍为 O(n²)；若改成随机基准，最坏情况概率极低，平均仍为 O(n log n)。刷到类似题先问：基准怎么选？数组是否已有序？就能避开"默认平均情况"的惯性思维。