用直接插入排序方法对序列{15,11,9,10,13}进行排序,关键码比较次数是 ______。A.10B.8C.4D.9

Question

用直接插入排序方法对序列{15，11，9，10，13}进行排序，关键码比较次数是 ______。

A．10

B．8

C．4

D．9

Answer 1

正确答案：B
解析：直接插入排序的基本算法是：当插入第i(i＞=1)个对象时，前面的V[0]，V[1]……V[i-1]已经排好序，这时，用v[i]的关键码与V[i-1]，V[i-2)，……的关键码顺序进行比较，找到插入位置即将v[i]插入，原来位置上的对象则向后移。本题中的i只能取1：第1趟(i=1)：11和15比较，插入：11，15，9，10，13第2趟(i=2)：9和11比较，插入：9，11，15，10，13第3趟(i=3)：10和9比较，不插入，再和11比较，插入：9，10，11，15，13第4趟(i=4)：13和9比较，不插入，和10比较，不插入，和11比较，不插入，和15比较，插入，排序完成。共比较8次。