问题
单项选择题
用直接插入排序方法对序列{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),(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趟(1=3):10和9比较,不插入,再和11比较,插入:9,10,11,15,13;第4趟(I=4):13和9比较,不插入,再和10比较,不插入,和11比较,不插入,和15比较,插入,排序完成。共比较8次。