GESP 五级 · GESP 202409 C++ 五级 第 9 题

假设快速排序算法的输入是一个长度为 $n$ 的已排序数组，且该快速排序算法在分治过程总是选择第一个元素作为基准元素。下面选项（ ）描述的是在这种情况下的快速排序行为。

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

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

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

【考纲定位】GESP 五级《算法与数据结构》模块第 4 章排序算法，考点为快速排序最坏情况。命题人卡住的是"排序数据≠快速排序快"的直觉误区。

【解题思维】看到"已排序数组"和"第一个元素为基准"，立刻判定：基准是最小值，划分后左子数组为空，递归深度达到 n，总比较次数 n+(n-1)+⋯+1=O(n²)。通法是：固定基准+已排序/逆序数据=快速排序最坏情形。

【陷阱拆解】选项 A 错在把"输入有序"等同于"算法快"，忽略了基准选择；选项 B 错在默认平均情况；选项 D 错在认为快速排序无法处理有序数据。最阴险的细节是"总是选择第一个元素"——一旦基准固定且输入有序，快速排序退化为线性划分，复杂度从O(n log n)跌至O(n²)。

【反命题思维】如果把基准改为中间元素或随机选取，有序数组下快速排序仍保持O(n log n)；若把数组改为逆序，同理会触发最坏情况。