NOIP 普及 2013 第一轮 第 14 题：平均时间复杂度为 O(n log n) 的排序

题目

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

选项

• A. 快速排序
• B. 插入排序
• C. 冒泡排序
• D. 基数排序

答案

A

题解

考点定位

本题考「排序平均复杂度」,对应大纲 4.1.3 排序（难度【1】）。

解题过程

平均 O(n log n)：快速排序（插入/冒泡平均 O(n²)；基数 O(d(n+r))）。

选 A。

易错提醒

① 快排平均 O(n log n)、最坏 O(n²)；② 「平均」二字是本题的题眼。