单选题
在待排序的元素序列基本有序的前提下,效率最高的排序算法是______。
A.插入排序 B.选择排序 C.快速排序 D.归并排序
【正确答案】
A
【答案解析】插入排序:待排序元素基本有序时,每次往前插入,比较和移动的次数都比较少。正序时时间代价为O(n),所以越趋于正序,时间代价越趋于O(n)。
选择排序:待排序元素有序和无序情况下,每次都要走遍剩余段,有序情况下就会出现许多无意义的比较。时间代价仍为O(n2)。
快速排序:待排序元素越有序,时间代价越大。正序时为O(n2)。
归并排序:待排序元素基本有序的情况下,主要时间消耗在数组的来回复制上,无意义的时间代价仍然很大。时间代价仍为O(nlog2n)。
所以答案为A。