GESP 五级 · GESP 202503 C++ 五级 第 21 题

快速排序算法的时间复杂度与输入是否有序无关，始终稳定为 $ O(n \log n) $。

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

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

【考点】排序算法｜时间复杂度分析｜最坏情况

🎯 考纲定位 GESP 五级《算法与数据结构》模块“排序与搜索”章节。命题人专卡“平均复杂度≠最坏复杂度”的认知盲区：很多考生死记“快速排序 O(n log n)”，却对已排序/逆序等极端情形下的退化无感。

🧠 解题思维 看到“始终稳定为”先怀疑绝对化表述；回忆快速排序选择枢轴的方式：若枢轴总是最小/最大元素，划分后一边为空，递归深度变为 n，退化为冒泡式 O(n²)。因此“不管输入是否有序”这一条件被命题人故意用来触发最坏情形。 通法：分析排序算法时，分三步——最好/平均/最坏，并给出对应枢轴选取策略。

🪤 陷阱拆解 错误选项 B 中的“始终稳定”是绝对化陷阱，命题人利用考生对“平均复杂度”的熟悉度，掩盖最坏情形；没有考虑已排序、逆序、全相同等边界输入。若只背结论不追枢轴机制，必掉坑。

🔄 反命题思维 若把题干改成“快速排序平均时间复杂度为 O(n log n)”，则答案为正确；若改成“快速排序是稳定排序”，则答案为错误。刷到类似题先问自己：命题人想考我用的是平均还是最坏？枢轴怎么选？