阅读下列算法说明和算法,将应填入(n)处的语句写在对应栏内。 【说明】为了减少直接插入排序关键字的

阅读下列算法说明和算法，将应填入(n)处的语句写在对应栏内。

【说明】

为了减少直接插入排序关键字的比较次数，本算法使用了二分(折半)插入法对一个无序数组R[1..n]进行排序。排序思想是对一个待插入元素，先通过二分法(折半)找到插入位置，后移元素后将该元素插入到恰当位置。(假设R[]中的元素互不相同)

[算法]

1．变量声明

X: Data Type

i,j,low, high,mid,r:0..n

2．每循环一次插入一个R[i]

循环：i以1为步长，从2到n，反复执行。

(1)准备

X←R[i];(1); high←i-1;

(2)找插入位置

循环：当(2)时，反复执行。

(3)

若X.key＜R[mid].key

则high←mid-1;

否则 (4)

(3)后移

循环：j以-1为步长，从(5)，反复执行。

R[j+1]←R[j]

(4)插入

R[low]←X

3．算法结束