排序题。。。。在待排序文件已基本有序的前提下，下列排序方法中效率最高的是（）。A）直接插入排序B）直接选择排序C）快速排序D）归并排序E）起泡排序。怎么判断？

Question

排序题。。。。
在待排序文件已基本有序的前提下，下列排序方法中效率最高的是（ ）。
A）直接插入排序 B）直接选择排序
C）快速排序 D）归并排序
E）起泡排序。
怎么判断？

Answer 1

选择A。选B的话，比较次数基本不变，还需要进行n^2级别的比较次数。选C的话，基本有序的情况下是快速排序最差的情况，时间复杂度和选择排序相差无几，选D的话，时间复杂度稳定，一直都是O(nlogn)，基本有序的文件对这个复杂度没影响。选E的话，参见B的解释。在文件基本有序的情况下，A是最好的，因为比较次数非常小。