NOIP 提高 2017 第一轮 第 16 题：以下排序算法在最坏情况下时间复杂度最优的有（ ）

题目

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

答案

C、D

题解

考点定位

本题考「最坏复杂度最优（不定项）」,对应大纲 4.1.3 排序（难度【1】）。

解题过程

最坏 O(n log n)：归并排序 ✓、堆排序 ✓；冒泡/快排最坏 O(n²)。

答案：C、D。

易错提醒

① 「最坏情况下最优」= 比较排序下界 O(n log n) 达成者；② 快排只有平均好。