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