GESP 七级 · GESP 202506 C++ 七级 第 18 题

对 $n$ 个元素的数组进行快速排序，最差情况的时间复杂度为 $O(n \log n)$。

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

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

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

【解题思维】 快速排序最坏情况发生在每次划分都极不平衡（如已排序数组且固定取首元素为基准）。此时递归深度达 $n$，每层代价 $O(n)$，总复杂度递推为 $T(n)=T(n-1)+O(n)=O(n^2)$。$O(n\log n)$ 是平均或最优情况，命题人故意用"最差情况"混淆视听。

【陷阱拆解】 选 A 的考生大多死记"快速排序是 $O(n\log n)$"，却未区分场景。题目最阴险之处在于把"最坏"与"平均"混为一谈，属于概念偷换。若只背结论不推导，必然掉坑。

【反命题思维】 将"最差情况"改为"最优情况"即变 A；换成"堆排序"或"归并排序"仍为 A；若限定"已排序数组且固定基准"则仍为 A；若改用"中位数三分"选基准，最坏概率趋近 0 但理论仍为 $O(n^2)$。刷到此类题先问"命题人想考我什么"。