CSP 模拟 · CSP 2020 第一轮（初赛）模拟 第 12 题

以下哪种排序算法的时间复杂度是 $O(n^2)$？

别急着背公式，先想命题人为什么把这几个排序放一起考？它们都是经典算法，但时间复杂度差异巨大。这道题考的是对排序算法本质的理解：是不是比较排序、最坏情况下的操作次数。拿到题，脑子里过一遍每个算法的核心逻辑，就能一眼锁定答案。

最容易栽跟头的就是把希尔排序和归并排序的时间复杂度搞混。希尔排序虽然比冒泡快，但它本质还是基于比较的，最坏情况依然是 O(n^2)，只是平均情况好很多，很多人看到它比冒泡快就误以为它是 O(n log n) 或者 O(n)。归并排序大家通常记得是 O(n log n)，但偶尔有人会把它和计数排序的 O(n+k) 搞混，或者误以为计数排序是 O(n log n)。还有人选 A 计数排序，是因为没看清题干问的是‘哪种’，以为所有非比较排序都是 O(n)，其实计数排序的时间复杂度是 O(n+k)，k 是数值范围，当 k 很大时就不是 O(n) 了，而且它根本不是比较排序，和题目问的‘时间复杂度是 O(n^2) 的排序’不沾边。

这道题考查的是排序算法的时间复杂度，尤其是比较排序与非比较排序的区别，以及常见算法的最坏情况复杂度。命题人喜欢把几个名字相似或容易混淆的排序放在一起，比如希尔排序和归并排序，都带‘希尔’或‘归并’字眼，但复杂度天差地别；还有计数排序，名字听起来像 O(n)，其实它的时间复杂度是 O(n+k)，k 是数值范围，当 k 很大时就不是 O(n) 了，而且它不是比较排序，和题目问的‘时间复杂度是 O(n^2) 的排序’不沾边。所以这道题的核心不是死记硬背，而是理解每个算法的本质：是不是比较排序、最坏情况下比较或移动次数是多少。拿到题，脑子里先过一遍每个选项的核心逻辑：计数排序按值分桶，不涉及比较，复杂度 O(n+k)；插入排序每轮把当前元素插入前面有序序列，最坏是 O(n^2)；希尔排序是插入排序的改进版，用间隔序列加速，最坏还是 O(n^2)，平均 O(n^{1.5}) 或更好；归并排序是分治，合并阶段 O(n)，递归深度 log n，总复杂度 O(n log n)。这样逐项对比，就能发现只有插入排序在最坏情况下严格是 O(n^2)，而且它是比较排序，符合题意。避坑指南：别被希尔排序的平均性能迷惑，也别把计数排序当成 O(n^2)，它根本不是比较排序。考频趋势：从历年 CSP-J/S 真题看，排序算法的时间复杂度是高频考点，尤其是插入排序、冒泡排序、选择排序的 O(n^2) 特性，几乎每年都会以单选或填空形式出现，最近三年连续考查过至少两次。预测：基于这个考频和命题人的偏好，未来大概率还会继续考排序算法的时间复杂度，可能会换个角度，比如问‘哪种排序在数据基本有序时最快’或者‘哪种排序是稳定且 O(n log n)'，但 O(n^2) 的插入排序这种基础概念题应该不会轻易放过，毕竟它是入门必会的。所以，记住：插入排序是 O(n^2)，希尔排序最坏也是 O(n^2)，归并排序是 O(n log n)，计数排序是 O(n+k)。