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

快速排序和归并排序的平均时间复杂度都是 $ O(n \log n) $，但快速排序是不稳定的排序算法，归并排序是稳定的排序算法。

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

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

【考点】快速排序｜归并排序｜排序稳定性

考纲定位：GESP 八级《算法与数据结构》模块，命题人卡住的是大量考生只背时间复杂度公式、却对稳定性概念模糊不清的弱点。

解题思维：看到"平均时间复杂度 O(n log n)"先想：快速排序最坏 O(n²) 但平均值确实是 O(n log n)；归并排序无论输入都严格 O(n log n)。再想"稳定性"：定义是相等元素排序前后相对位置不变。快速排序原地分区会打乱相等元素顺序，归并排序合并时优先保留原顺序，因此前者不稳定后者稳定。此类题通法：先确认复杂度断言是否成立（看最坏/平均/最好），再对照稳定性定义判断算法行为。

陷阱拆解：错误选项 B 的陷阱在于考生容易把"快速排序不稳定"当成绝对事实，而忽略它只是平均 O(n log n) 且稳定性的结论成立。命题人利用的误区是混淆"最坏情况 O(n²)"与"平均情况 O(n log n)"，以及误以为归并排序可能不稳定。细节上，"平均"二字是绝对化表述，若换成"最坏"就全错，这正是命题人埋的坑。

反命题思维：如果题目改成"快速排序的最坏时间复杂度是 O(n log n)"，答案立刻变错；或者把"稳定性"换成"原地性"，归并排序就不是原地算法。刷题时先问自己：命题人想考我什么——是考复杂度分类，还是考算法特性辨析。