GESP 五级 · GESP202609 C++ 五级 第 22 题

快速排序中如果选取区间第一个元素作为枢轴。当输入数组已经升序排列时，其最坏时间复杂度仍为 $O(n \log n)$。

看到题先想什么？看到"快速排序"、"枢轴是第一个元素"、"已升序排列"，立刻想到：每次分区都会把枢轴放到最右边，导致递归深度为 n，每层 O(n) 操作，总复杂度 O(n²)。

命题人利用"快速排序平均 O(n log n)"的常识，故意把"最坏情况"和"平均情况"混淆。学生容易想当然认为"快速排序就是 O(n log n)"，忽略了枢轴选择对最坏情况的影响。

1. 考纲定位

本题考查《GESP 考试大纲》五级"算法与数据结构"模块中快速排序的最坏时间复杂度分析。命题人卡住的是考生对"枢轴选择策略如何影响复杂度"这一深层理解的缺失——五级考生往往只会背"快速排序 O(n log n)"，却不懂这个结论成立的前提条件。

2. 解题思维

快速排序的核心是分区操作：选定枢轴后，把小于枢轴的放左边、大于的放右边。当枢轴固定为第一个元素且数组已升序时，分区结果必然是：左边为空，右边为剩余所有元素（因为所有元素都≥枢轴）。这意味着每次递归调用只减少一个元素，递归深度达到 n 层。每层分区耗时 O(n)，总时间复杂度为 O(n²)。