GESP 五级 · GESP 202603 C++ 五级 第 13 题

有 $n$ 位同学的成绩已经从小到大排好序，现在对它执行下面这段以第一个元素为 pivot 的快速排序，请问此次排序的时间复杂度是（ ）。

void quicksort(vector<int>& a, int l, int r) {
    if (l >= r) return;
    int pivot = a[l];
    int i = l, 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]);
    }
    swap(a[l], a[i]);
    quicksort(a, l, i - 1);
    quicksort(a, i + 1, r);
}

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

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

【考点】快速排序｜最坏情况时间复杂度｜已排序数组特性

1. 🎯 考纲定位 GESP 五级算法模块的典型陷阱题。命题人卡住的是"只会背 O(n log n) 平均复杂度"的考生——他们知道快速排序平均是 O(n log n)，但没意识到当输入已有序且固定选第一个元素为 pivot 时，每次划分都极端失衡，退化成链表式递归。

2. 🧠 解题思维

• 数组已从小到大排序，pivot = a[l] 就是当前子段最小值
• 划分过程：j 从右往左找 < pivot 的数，但所有数都 ≥ pivot，直到 j 撞到 l；i 从左往右找 > pivot 的数，一直冲到 r
• 结果：所有非 pivot 元素要么在左段要么在右段，pivot 最终停在位置 0
• 左段长度 = 0，右段长度 = n−1
• 递归：quicksort(a, l, i−1) 立刻返回，quicksort(a, i+1, r) 处理 n−1 个元素
• 递推式：T(n) = T(n−1) + O(n) → T(n) = O(n²)

3. 🪤 陷阱拆解

• 选 A O(n)：混淆了线性扫描与排序，快速排序无论如何调用两次递归，至少 O(n log n)
• 选 B O(n log n)：这是平衡划分（pivot 每次把数组一分为二）的平均情况，本题恰恰是极端不平衡
• 选 D O(log n)：压根不是排序复杂度量级，连二分查找的 O(log n) 都搞不清
• 最阴险处：代码里的 while 循环看似会遍历整个数组，但考生容易忽略"已排序 + 固定 pivot"导致划分后一边为空，递归深度直接变成 n 层

4. 🔄 反命题思维 若把 pivot 改成随机选（或选中间位置），已排序数据也能避免最坏情况，复杂度回归 O(n log n)。刷到类似题先问：pivot 怎么选？输入是否特殊？划分后左右段长度比例如何？