用折半插入排序算法，解决例1.

Question

用折半插入排序算法，解决例1.

Answer 1

思路分析：用折半插入排序法将一新数据插入到一有序列中，就是反复运用“折半”思想，寻找新数据所在的位置的过程.

用折半插入排序法，设计算法步骤如下：

第一步：把新数据38与“中间位置”的数据26比较，由于38＞26，所以应将38放到26的右边的一半有序列中，即应放到有序列37，39，46，70中.

第二步：把38与有序列37，39，46，70“中间位置”的数据39比较，由于38＜39，所以应将38放到39的左边的一半有序列中，即应放到有序列37，39中.

第三步：把38与有序列37，39“中间位置”的数据37比较，由于38＞37，所以应将38放到37的右边的一半有序列中，至此排序完成，得到一新的有序列

10 13 18 26 37 38 39 46 70

温馨提示

    有序插入排序法就是先比较两个数的大小，再把其余的数依次进行比较插入到这个数列中.而折半插入排序法是先将新数据与“中间位置”的数据进行比较，把原有序列折半，直到确定新数据应有的位置.