问题 单项选择题

用直接插入排序方法对序列{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次。

解答题
单项选择题