NOIP 提高组初赛 · NOIP 2017 提高组初赛试题 第 16 题

以下排序算法在最坏情况下时间复杂度最优的有（ ）。

这题直接看最坏情况。冒泡和快排最坏都得 O(n²)，只有归并和堆排能保证最坏也是 O(n log n)，所以选 CD。

很多同学容易把快排的平均复杂度当成最坏，觉得快排肯定快就选了它，结果掉进命题人挖的坑里。还有的会误以为冒泡排序在数据基本有序时表现好，所以最坏情况也还行，其实冒泡最坏就是 O(n²)。

考点概念：排序的最坏时间复杂度

这道题考查的是排序算法的时间复杂度，特别是最坏情况下的复杂度。冒泡排序、快速排序、归并排序、堆排序是最常见的几种排序算法，它们的时间复杂度各有特点。

命题视角：为什么考最坏情况

命题人喜欢考最坏情况，是因为平均情况往往太理想化，实际应用中更关心极端情况。比如快排平均 O(n log n) 很诱人，但一旦遇到特殊情况就变 O(n²)，这在算法竞赛中是致命的。