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