2009年5月程序员笔试考前练习（43）
读书人IT频道reader8.net/exam/jisuanji/ 阅读下列算法说明和算法，将应填入(n)处的语句写在答题纸的对应栏内。 【说明】 为了减少直接插入排序关键字的比较次数，考试#大提示本算法使用了二分(折半)插入法对一个无序数
读书人IT频道reader8.net/exam/jisuanji/ 阅读下列算法说明和算法，将应填入(n)处的语句写在答题纸的对应栏内。
【说明】
为了减少直接插入排序关键字的比较次数，考试#大提示本算法使用了二分(折半)插入法对一个无序数组R［1..n］进行排序。排序思想是对一个待插入元素，先通过二分法(折半)找到插入位置，后移元素后将该元素插入到恰当位置(假设R［］中的元素互不相同)。
【算法】
1．变量声明
X：DataType
i，j，low，high，mid，R0..n
2．每循环一次插入一个R［i］
⊙罚篿以1为步长，从2到n，反复执行
①准备
X<-R［i］； (1) ；high<-i-1；
②找插入位置
循环：当 (2) 时，反复执行
(3)
若X．key
则high<-mid-1
否则 (4)
③后移
循环：j以-1为步长，从 (5) ，反复执行
R［j+1］<-R［j］
④插入
R［low］<-X
3．算法结束
【答案】
(1)low<-1
(2)low≤high
(3)mid<-int((low+high)/2)
(4)low<-mid+1
(5)i-1到low 读书人IT频道reader8.net/exam/jisuanji/
