折半插入排序的總體思想是：

a[i]和前面a[0]到a[i-1]的有序數(shù)中間位置的數(shù)比較大小

如果a[i]大于中間位置的值，就把有序數(shù)的左端點(diǎn)往右移到中間位置的下一位

如果小于中間位置的值，就將有序數(shù)的右端點(diǎn)往左移到中間位置的前一位，一直重復(fù)進(jìn)行比較

直到左端點(diǎn)的位置大于右端點(diǎn)的位置，此時(shí)確定要插入的位置就是右端點(diǎn)的下一位

將a[i-1]到a[i]要插入的位置的數(shù)集體向后移動(dòng)一位

將a[i]插入找到的位置

至于為什么插入位置是右端點(diǎn)的下一位，以下舉例解釋：

38，69，45，97，76，13，27

a[2]進(jìn)行插入排序，左端點(diǎn)位置是0，右端點(diǎn)位置是1，中間位置是(0+1/2=0),l,m都在0的位置，h在1的位置，45>38,左端點(diǎn)往右移l,m,h都在1的位置，45<69,右端點(diǎn)往左移，h在0的位置，l在1的位置，此時(shí)l>h比較結(jié)束，45應(yīng)插入38的后面，即h的下一位。

代碼如下：