CSP-S 2022 第一轮 第4题：考虑对n个数进行排序，以下最坏时间复杂度低于0(n²)的排序方法是（)。

题目

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

选项

• A. 插入排序
• B. 冒泡排序
• C. 归并排序
• D. 快速排序

答案

C

题解

答案是 C. 归并排序。关键在于题目问的是最坏时间复杂度。

归并排序每次把数组分成两半，共有约 $\log n$ 层，每层合并需要 $O(n)$ 时间，因此总时间复杂度是 $O(n\log n)$，低于平方级。

容易误选的是 D：快速排序的平均时间复杂度是 $O(n\log n)$，但如果每次选出的基准都是当前最小值或最大值，划分就会极不均衡，最坏会退化为 $O(n^2)$。