折半插入排序的总体思想是：
a[i]和前面a[0]到a[i-1]的有序数中间位置的数比较大小
如果a[i]大于中间位置的值，就把有序数的左端点往右移到中间位置的下一位
如果小于中间位置的值，就将有序数的右端点往左移到中间位置的前一位，一直重复进行比较
直到左端点的位置大于右端点的位置，此时确定要插入的位置就是右端点的下一位
将a[i-1]到a[i]要插入的位置的数集体向后移动一位
将a[i]插入找到的位置
至于为什么插入位置是右端点的下一位，以下举例解释：
38，69，45，97，76，13，27
a[2]进行插入排序，左端点位置是0，右端点位置是1，中间位置是(0+1/2=0),l,m都在0的位置，h在1的位置，45>38,左端点往右移l,m,h都在1的位置，45<69,右端点往左移，h在0的位置，l在1的位置，此时l>h比较结束，45应插入38的后面，即h的下一位。
代码如下：
网友评论