Question

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

A.A）88、90、36、90、96、53、41、57
B.B）22、50、11、34、65、94、21、47
C.C）23、25、46、50、80、69、90、94
D.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）。