问题 单项选择题

在文件“局部有序”或文件长度较小的情况下,最佳内部排序方法是______。

A.直接插入排序

B.冒泡排序

C.简单选择排序

D.归并排序

答案

参考答案:A

解析:
当待排序列基本有序时:
①直接插入排序在待排序列基本有序时,每趟的比较次数大为降低,也即n-1趟比较的时间复杂度由O(n2)降至O(n)。
②对冒泡排序来说,若最大关键字位于序列首部,则每趟排序仅能使其“下沉”一个位置,要使其下沉到底部仍需n-1趟排序,也即时间复杂度仍为O(n2)。
③对简单选择排序来说,其比较次数与待排序列的初始状态无关。
④归并排序要求待排序列已经部分有序,而部分有序的含义是待排序列由若干有序的子序列组成,即每个子序列必须有序,并且其时间复杂度为O(nlog2n)。
综上所述,本题正确答案为选项A。

单项选择题
填空题