GESP 五级 · GESP 202603 C++ 五级 第 14 题

下面关于排序算法的描述中，不正确的是（ ）。

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

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

【考点】排序稳定性｜时间复杂度

1. 考纲定位 GESP 五级 P2 模块核心考点。命题人专挖"归并排序稳定性"这个知识盲区，90% 考生会误以为快速排序和归并排序都不稳定，因为 Quick Sort 确实不稳定，但 Merge Sort 通过合并时稳定比较保证了稳定性。

2. 解题思维 逐条验证：A 项冒泡和插入排序在相等元素顺序不变时确实稳定；C 项当输入已有序时，冒泡只需一次扫描 O(n)，插入排序也只需 O(n)；D 项归并排序分治递归深度 log n，每层 O(n)，三种情况都是 O(n log n)。唯独 B 项把归并排序划入不稳定是错误的。

3. 陷阱拆解 陷阱在于"都是"这个绝对化表述，一旦知道归并排序稳定，B 项立刻崩塌。很多学生死记"快速排序不稳定"，却忘了归并排序的特殊性，这是典型的"以偏概全"思维陷阱。

4. 反命题思维 若把 B 项改为"快速排序和堆排序都不稳定"，答案仍为 B；若把 C 项改为"冒泡排序和插入排序最坏时间复杂度均为 O(n)"，则 C 项变为错误。刷到此类题先问："命题人想考我哪个算法的稳定性？"