GESP 五级 · GESP 202409 C++ 五级 第 20 题

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

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

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

【考点】排序算法｜稳定性

本题考查《GESP 考试大纲》五级"排序算法"模块，命题人特意用"稳定性"这一易混淆属性，卡住只会背时间复杂度的考生。该题在五级试卷中属于算法综合题，不仅要求记住时间复杂度，更要理解排序算法的内在特性。

看到题先拆解两个命题：快速排序和归并排序的平均时间复杂度确实都是 O(n log n)，但稳定性截然不同——归并排序通过合并子序列保持相等元素顺序，是稳定排序；快速排序因交换操作会打乱相等元素相对位置，是典型不稳定排序。归并排序的核心在于分治合并，相等元素始终按原顺序进入新序列；快速排序的核心在于分区交换，相等元素可能因枢轴选择而跨分区，破坏原始顺序。

陷阱在于把"平均时间复杂度"和"稳定性"混为一谈：命题人利用考生对稳定性的陌生感，用"且都是稳定排序"这一绝对化表述制造逻辑陷阱，若只背结论而不理解算法本质，就会误判为正确。许多考生只记住了"快速排序 O(n log n)"，却忽略了"不稳定"这一关键属性，导致看到题目后半句时，误以为两个排序都稳定。

若命题人把"快速排序"换成"插入排序"，则前半句"平均时间复杂度 O(n log n)"变为"O(n²)"，整体仍为错误。若把"稳定"换成"不稳定"，则后半句变为"都是不稳定排序"，此时快速排序符合，归并排序不符合，答案仍为错误。