GESP 五级 · GESP 202606 C++ 五级 第 25 题

归并排序和快速排序在平均情况下的时间复杂度均为 $O(n \log n)$。但在稳定性方面，归并排序通常是不稳定的，而快速排序是稳定的。

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

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

【身份】｜ 【考点】排序稳定性｜时间复杂度分析｜算法比较

🎯 考纲定位：本题考查《GESP 五级 C++ 算法模块》中排序算法的稳定性辨析。命题人把“归并排序稳定”和“快排不稳定”两个反常识结论颠倒，卡住的是只背“快排 O(n log n)”却不懂稳定性的考生。

🧠 解题思维：看到“稳定性”三个字，先回忆两类排序的核心操作：归并排序合并时遇到相等元素，默认保持原顺序（稳定）；快排序分区时交换元素，相等键值可能前后互换（不稳定）。题目把结论全反了，所以直接选 B。这一类题的通法是：先锁定算法的“操作细节”，再对照“相等元素是否保持相对次序”来判断稳定性。

🪤 陷阱拆解：选项 A 的陷阱在于“平均 O(n log n)"是两人都满足的，命题人用这个共同点迷惑你，让你以为“既然时间复杂度一样，那稳定性也差不多”。选项 B 才是正解。最阴险的细节是“通常”二字——归并排序在标准实现里是稳定的，但有些教材会提“不稳定”的版本（比如合并时随意选择相等元素），快排序却永远不稳定。只背“快排好”“归并慢”的结论，就会掉进这个坑。

🔄 反命题思维：站在命题人角度：如果把“通常是不稳定的”改成“通常是稳定的”，答案就反了；如果把“快排序是稳定的”改成“快排序在最坏情况下是 O(n^2)"，考点就变成“平均 vs 最坏”。刷到类似题，先问自己“命题人想考我什么”——是稳定性、时间复杂度还是两者混搭？