CSP-S 提高级 · CSP 2022 提高级第一轮 第 4 题

考虑对 n 个数进行排序，以下最坏时间复杂度低于 $O(n^2)$ 的排序方法是（ ）。

看到‘最坏’二字立刻警觉，四个选项里只有归并排序是无论数据怎么摆、递归深度固定为 log n，合并每层线性扫一遍，稳稳卡在 O(n log n)，其余三个平均再好，最坏都能退化成平方级，所以答案只能是 C。

最容易栽跟头的就是盯着快速排序的平均复杂度 O(n log n) 就选它，完全忽略了题目问的是‘最坏’。快排一旦遇到已排好序或逆序的数据，若 pivot 选得不好，递归深度会崩成 n 层，总代价直接飙到 O(n²)。另外，插入排序和冒泡排序虽然平均也是 O(n²)，但它们最坏同样是 O(n²)，所以更不能选。记住：排序题里‘最坏’往往是最坑的陷阱，千万别只看平均。

考点定位：这道题考查排序算法的时间复杂度，尤其是‘最坏情况’的判别能力。命题人特意把平均和最容易混淆的快排放在同一个选项里，就是想看你是否会掉进‘平均好就选’的陷阱。

概念拆解：所谓最坏时间复杂度，就是输入数据让算法跑得最慢的那一种情况。比如快排，如果每次选到的 pivot 都是当前区间的最小值或最大值，那每次只能把区间缩小 1 个元素，递归深度变成 n，总复杂度就是 O(n²)。而插入排序和冒泡排序，无论数据怎么排，比较次数都是 O(n²) 级别，所以它们的最坏和平均都是平方级。

归并排序为什么稳：归并排序用的是分治策略——先把数组对半切开，递归地对左右两半排序，然后再把两个有序子数组合并。关键在于，不管原始数据乱不乱，递归的层数永远是 log₂n 层（因为每次对半切），每层合并都要扫描整个数组，代价是 O(n)。所以总复杂度严格等于 O(n log n)，没有‘退化’一说。

思考路径：拿到题先扫一眼四个名字。插入、冒泡、快排，这三个一听就是‘容易退化成平方’的；归并一听就是‘分治 + 合并’，分治的层数是固定的，合并是线性的，所以最坏也跑不了 O(n log n)。题目问的是‘最坏低于 O(n²)'，那只有归并符合。

避坑提醒：学生常犯的错误是看到快排平均 O(n log n) 就选它，完全忽略‘最坏’二字。还有的是把插入排序的最坏当成 O(n log n)，其实插入排序最坏就是 O(n²)，因为每次只能插入一个元素到正确位置，比较次数是 n(n-1)/2。

考频与趋势：从题库数据看，排序相关题目一共考过 249 题，覆盖 9 个级别，逐年分布从 2008 年的 2 题一路涨到 2026 年的 50 题，2025 年更是飙到 57 题，说明排序是高频考点。其中归并排序单独考了 51 题，分布从 2009 年的 2 题到 2026 年的 9 题，2024、2025 两年分别考了 14 题和 15 题，呈现明显的上升趋势。分赛事看，GESP 五级考了 33 题，占比最大，其次是 GESP 八级 8 题、CSP 提高级 3 题等。

未来预测：基于归并排序近年考频持续攀升（2024-2026 三年合计 38 题，远超其他年份），且 CSP 提高级、GESP 五级等核心赛场都在频繁出现，未来这类‘最坏复杂度’的概念辨析题大概率会继续高频出现，甚至可能结合具体代码实现或稳定性判断来加深难度。暂无足够依据预测具体年份或题型变化，但趋势明确：排序算法的复杂度分析仍是必考重点。