GESP 八级 · GESP 202509 C++ 八级 第 18 题

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

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

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

【考点】数组排序｜时间复杂度分析｜比较排序下界

🎯 考纲定位 本题考查 GESP 八级《算法设计与分析》模块中“排序算法复杂度”知识点。命题人专门设置这道判断题，就是要卡住那些只背过冒泡排序、插入排序的考生——他们死记 $O(n^2)$ 却不知合并排序的存在，把"部分算法的最差情况"误当成"所有排序算法的通用结论"。

🧠 解题思维 看到"排序"二字，立刻联想比较排序家族：冒泡、插入、选择确实是 $O(n^2)$，但合并排序、堆排序能稳定在 $O(n \log n)$。命题人故意用"最差情况"这个模糊表述，诱导考生只盯着 $O(n^2)$ 的算法。正确思路是：只要存在一个排序算法在最坏情况下优于 $O(n^2)$，原命题即为假。实际上，任何基于比较的排序算法，其最坏情况复杂度都不可能低于 $O(n \log n)$。

🪤 陷阱拆解 错误选项 A 的诱惑力在于：冒泡排序、选择排序、插入排序这三种基础算法确实都卡在 $O(n^2)$。命题人利用考生"只背常用算法"的思维惰性，故意省略了"所有"二字，让考生误以为这是通用结论。更阴险的是，题目用"最差情况"模糊了算法种类——如果你只记住 $O(n^2)$ 的排序，没接触过合并排序，就会掉进这个语义陷阱。

🔄 反命题思维 站在命题人角度，这道题的本质是考"比较排序的下界"。如果题目改成"存在一种排序算法，其最坏情况复杂度为 $O(n \log n)$"，答案就是 A；如果改成"所有排序算法的最坏情况复杂度都是 $O(n^2)$"，答案就是 B。刷到这类题，先问自己：命题人在考算法种类还是考复杂度边界？