用直接插入排序法对下面四个序列由小到大进行排序,元素比较次数最少的是( )。A)88、90、3

Question

用直接插入排序法对下面四个序列由小到大进行排序，元素比较次数最少的是（ ）。

A)88、90、36、90、96、53、41、57

B)22、50、11、34、65、94、21、47

C)23、25,46、50、80、69、90、94

D)90、85、14、43、73、21、52、96

Answer 1

正确答案：C
直接插入排序的基本算法是：当插入第i(i>=1)个对象时，前面的a[0]，a[1] ……a[i-1]已经排好序，这时，用a[i]的关键码与a[i-1]，a[i-2]，……的关键码顺序进行比较，找到插入位置即将a[i]插入，原来位置上的对象则向后移。因此，直接插入排序法的关键码比较次数与对象的初始排列有关(若第i个对象之前的i-1个对象已经按顺序排好，则只需与第i-1号对象比较后即可停止比较，故比较次数较少)。对于本题来说，选项A)中i可以取2，选项B)中i可以取2，选项C)中i可以取5，选项D)中i可以取1。因此本题选择选项C)。