选择题
16.
下列排序方法中，最坏情况下时间复杂度(即比较次数)低于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选项正确。
提交答案
关闭