选择题
3.
下列各组排序法中，最坏情况下比较次数相同的是______。
A、
简单选择排序与堆排序
B、
简单插入排序与希尔排序
C、
冒泡排序与快速排序
D、
希尔排序与堆排序
【正确答案】
C
【答案解析】
对于长度为n的线性表，最坏情况下查找或排序的次数如下表：
类型
最坏情况下查找或比较次数
时间复杂度
顺序查找
n
O(n)
查找最大项或最小项
n-1
O(n-1)
二分查找法
log
2
n
O(log
2
n)
冒泡排序法
n(n-1)/2
O(n(n-1)/2)
快速排序法
n(n-1)/2
O(n(n-1)/2)
简单插入排序法
n(n-1)/2
O(n(n-1)/2)
希尔排序法
n
r
(1＜r＜2)
O(n
r
))(1＜r＜2)
简单选择排序法
n(n-1)/2
O(n(n-1)/2)
堆排序
nlog
2
n
O(nlog
2
n)
提交答案
关闭