问题
单项选择题
用直接插入排序方法对序列{15,11,9,10,13}进行排序,关键码比较次数是
A.10
B.8
C.4
D.9
答案
参考答案: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次。