UC知道一道改进的直接插入排序填空题，回答被采纳加30分！谢谢。
来源：百度知道 编辑：UC知道 时间：2024/05/22 03:58:32
[说明]为了减少直接插入排序关键字的比较次数，本算法使用了二分(折半)插入法对一个无序数组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、算法结束
标准答案是：(1)low <- 1
(2)low <= high
(3)mid <- int((low+high)/2)
(4)low <- mid+1
(5)i-1到low
我只有一个问题，就是第二空：我填的是low < high，我认为这样填写也对，因为我举例子验证过了。大家说呢？
再多问一句，软考老师阅卷很严吗？如果第三空我写成了mid <- (low+high)/2是不是也能算对呢？因为我觉得“/”(实数除，C语言)本身除出来就是不大于(low+high)÷2的最大
[算法]
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、算法结束
标准答案是：(1)low <- 1
(2)low <= high
(3)mid <- int((low+high)/2)
(4)low <- mid+1
(5)i-1到low
我只有一个问题，就是第二空：我填的是low < high，我认为这样填写也对，因为我举例子验证过了。大家说呢？
再多问一句，软考老师阅卷很严吗？如果第三空我写成了mid <- (low+high)/2是不是也能算对呢？因为我觉得“/”(实数除，C语言)本身除出来就是不大于(low+high)÷2的最大
算法具体怎么写的忘记了，但是好像写成LOW<HIGH是不行的，好像有特例的情况，如果最后的LOW和HIGH相等了呢？那样好像会出问题吧。
还有，第三个问题为什么不要那么写的，因为不用的机器的编译环境不一样，如果不加强制类型转换的话，有的是默认舍掉的，也有的不是，所以加上为了不出问题。
至于判卷么。不好说，是等级考试还是软件设计分析师，后者的话要严格些
举例：比如说你插入的是5，8，3，6，1.
当第一次插入直插入一个5，第二次插入8的时候，low=high=1的，而第二个循环里面的找mid根本执行不到，所以没办法把8插入到相应位置的。
不是完整C的程序看着有点别扭，呵呵。