单选题
下列排序方法中，时间性能与待排序记录的初始状态无关的是______。
A、
插入排序和快速排序
B、
归并排序和快速排序
C、
选择排序和归并排序
D、
插入排序和归并排序
【正确答案】
C
【答案解析】
[解析] 考查各种内部排序算法的性能。选择排序在最好、最坏、平均情况下的时间性能均为O(n
2
)，归并排序在最好、最坏、平均情况下的时间性能均为O(nlog
2
n)。各种排序方法对应的时间复杂度见下表。快速排序在原序列本身有序的时候达到最坏的时间复杂度，直接插入排序在原序列本身有序的时候达到最好的时间复杂度。
时间复杂
直接插入
冒泡排序
简单选择
希尔排序
快速排序
堆排序
二路归并
平均情况
O(n
2
)
O(n
2
)
O(n
2
)
-
O(nlog
2
n)
O(nlog
2
n)
O(nlog
2
n)
最好情况
O(n)
O(n)
O(n
2
)
-
O(nlog
2
n)
O(nlog
2
n)
O(nlog
2
n)
最坏情况
O(n
2
)
O(n
2
)
O(n
2
)
-
O(n
2
)
O(nlog
2
n)
O(nlog
2
n)
提交答案
关闭