NOIP 提高组初赛 · NOIP 2014 提高组初赛试题 第 14 题

以下时间复杂度不是 $O(n^2)$ 的排序方法是( ).

这题很简单，直接背时间复杂度公式就行，记住O(n²)的四大排序和O(n log n)的三大排序，一眼就能排除B。

很多初学者容易混淆快速排序的最坏情况，以为快排永远是O(n log n)，或者把归并排序记成O(n²)，其实归并是稳态O(n log n)，而快排最坏才退化到O(n²)。

排序算法时间复杂度

考点：掌握常见排序算法的平均与最坏时间复杂度。

概念：

• O(n²)：意味着比较次数随数据量平方增长，典型代表是插入排序、冒泡排序、选择排序，它们都只在局部调整，没有分治思维。
• O(n log n)：意味着有分治策略，每次把问题规模减半，典型代表是归并排序、快速排序（平均）、堆排序。

命题视角： 命题人爱挖的坑有两个： 1. 把快速排序的最坏情况O(n²)当成常态，误以为快排和归并一样稳。 2. 把归并排序记成O(n²)，因为名字里带“归并”听起来像一步步合并，容易想复杂。

思考心法： 拿到题先想“这个排序有没有分治？”

• 归并排序：把数组一分为二，递归排序，再合并，合并是线性的，所以总复杂度是O(n log n)。
• 插入、冒泡、选择：都是两两比较，没有分治，所以是O(n²)。
• 快排：平均O(n log n)，但最坏O(n²)。

计算与结论： 题目问“不是O(n²)的排序方法”，四个选项里，A、C、D都是O(n²)，只有B归并排序是O(n log n)，所以选B。

避坑：

• 别把快排的最坏情况当成常态，快排平均是O(n log n)，最坏才O(n²)。
• 别把归并排序记成O(n²)，归并是稳态O(n log n)。

考频与趋势： 排序算法的时间复杂度是NOIP/CSP初赛的高频考点，题库共考过249题，覆盖9个级别。逐年分布：2008年2题、2009年3题、2010年3题、2011年1题、2012年2题、2013年1题、2014年2题、2015年1题、2017年2题、2018年1题、2019年1题、2020年2题、2021年3题、2022年5题、2023年22题、2024年51题、2025年57题、2026年50题、null年40题。分赛事：GESP五级74题、CSP入门级44题、GESP四级39题、GESP八级27题、GESP七级26题、GESP六级12题、NOIP提高组初赛12题、CSP提高级9题、NOIP普及组初赛6题。

预测： 从2023到2026年，排序相关题目数量明显上升（2023年22题、2024年51题、2025年57题、2026年50题），说明命题人越来越喜欢在排序上做文章，尤其是时间复杂度的辨析。未来大概率还会考“快排最坏情况”或“归并排序复杂度”这类题目，建议把O(n²)和O(n log n)的排序彻底背熟，做题时一眼就能排除。