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

Question

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

A．94、32、40、90、80、46、21、69

B．32、40、 21、46、 69、 94、 90、 80

C．21、 32、 46、 40、 80、 69、 90、 94

D．90、69、80、46、21、32、94、40

Answer 1

正确答案：C
解析：直接插入排序的基本算法是：当插入第i(i＞=1)个对象时，前面的v[0]，V[1]……v[i-1]已经排好序，这时，用V[i]的关键码与V[i-1]，V[i-2]，……的关键码顺序进行比较，找到插入位置即将V[i]插入，原来位置上的对象则向后移。由此可知，直接插入排序法的关键码比较次数与对象的初始排列有关，准确的说，就是与i可以取的值有关。对于本题来说，A中i可以取1，B中i可以取2，C中i可以取3，D中i可以取1。所以C的关键码比较次数最少。