问题
单项选择题
用直接插入排序方法对序列{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次。