2015年计算机软件水平程序员笔试考前练习精选（39）
发布时间：2012/11/4 15:34:40 来源：城市网学院 编辑：admin
阅读下列算法说明和算法，将应填入（n）处的语句写在答题纸的对应栏内。
【说明】
为了减少直接插入排序关键字的比较次数，提示本算法使用了二分（折半）插入法对一个无序数组R［1n］进行排序。排序思想是对一个待插入元素，先通过二分法（折半）找到插入位置，后移元素后将该元素插入到恰当位置（假设R［］中的元素互不相同）。
【算法】
1.变量声明
X：DataType
i，j，low，high，mid，R0n
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
