NOIP 普及组初赛 · NOIP 2013 普及组初赛试题 第 14 题

（ ）的平均时间复杂度为 $O(n \log n)$，其中 $n$ 是待排序的元素个数。

看到O(n log n)先别急着选，脑子里过一遍常见排序：快排、归并、堆排都是这个量级，而插入、冒泡是平方级，基数排序看k。这题考的是对‘平均’和‘最坏’的区分，命题人最爱把快排的平均好、最坏差放在一起挖坑，让你误以为它不如归并稳定，或者反过来。

最容易错的是把基数排序当成O(n log n)，其实它是O(nk)（k是关键字位数），除非题目明确说k是常数，否则不能直接等同。其次，有些同学会纠结快排的最坏O(n²)而不敢选，但题干只问平均，所以A完全正确。还有人会混淆归并和堆排，以为它们也是平均O(n log n)但最坏不同，其实归并和堆排都是无论什么输入都稳在O(n log n)，快排才是平均好最坏差的典型。

这道题考什么

考的是对常见排序算法时间复杂度的记忆，尤其是‘平均’与‘最坏’的区别。命题人特别喜欢用快排做陷阱：它的平均是O(n log n)，但最坏会退化到O(n²)。题目只问平均，所以答案很明确。

知识点回顾（人话版）

• 快速排序：选个基准把数组分成两半，递归排左右。平均每次划分比较均匀，所以是O(n log n)；如果每次划分极不均衡（比如已经有序却选第一个当基准），就会退化成O(n²)。
• 插入排序：把新元素插到已排好序的部分里，每次最多挪n次，总共O(n²)。
• 冒泡排序：两两比较交换，同样O(n²)。
• 基数排序：按位（或按关键字长度k）分桶再收集，复杂度O(nk)，k是关键字的位数或最大长度，不是log n。
• 归并排序 / 堆排序：无论什么输入，都是O(n log n)，没有最坏退化。