单选题
下列排序方法中，最坏情况下时间复杂度(即比较次数)低于O(n
2
)的是______。
A、
快速排序
B、
简单插入排序
C、
冒泡排序
D、
堆排序
【正确答案】
D
【答案解析】
[解析] 对长度为n的线性表排序，常用的排序方法最坏情况的时间复杂度如下表所示：
方法
最坏情况时间复杂度
冒泡排序
O(n
2
)
简单插入排序
O(n
2
)
简单选择排序
O(n
2
)
快速排序
O(n
2
)
堆排序
O(nlog
2
n)
由上表可知，时间复杂度低于O(n
2
)的排序算法是堆排序。故选择D。
提交答案
关闭