基本思想

折半插入排序是对直接插入排序的简单改进，对于直接插入排序而言。当第i-1趟须要将第i个元素插入前面的0~i-1个元素序列中时，总是须要从i-1个元素開始。逐个比較每一个元素，直到找到它的位置。这显然没有利用前面0~i-1个元素已经有序这个特点，而折半插入排序则改进了这一点。

对于折半插入排序而言，当须要插入第i个元素时，它不会逐个进行比較每一个元素。而是：

（1）计算0~i-1索引的中间点。也就是用i索引处的元素和(0+i-1)/2索引处的元素进行比較，假设i索引处的元素值大，就直接在(0+i-1)/2~i-1半个范围内进行搜索；反之在0~(0+i-1)/2半个范围内搜索，这就是所谓的折半。

（2）在半个范围内搜索时，依照（1）的方法不断地进行折半搜索，这样就能够将搜索范围缩小到1/2、1/4、1/8…，从而高速的确定插入位置；

---

Java实现代码

package com.liuhao.sort;import java.util.Arrays;public class BinaryInsertSort {    public static void binaryInsertSort(DataWrap[] data){        int arrayLength = data.length;                for(int i=1; i
     
       0){                    low = mid + 1;                }                else{                    high = mid - 1;                }            }                        // 依次后移            for(int j=i; j>low ; j--){                data[j] = data[j-1];            }                        data[low] = tmp;            System.out.println(Arrays.toString(data));        }    }        public static void main(String[] args) {        DataWrap[] data = {                 new DataWrap(21, "")                ,new DataWrap(30, "")                ,new DataWrap(49, "")                ,new DataWrap(30, "*")                ,new DataWrap(16, "")                ,new DataWrap(9, "") };        System.out.println("排序之前：" + Arrays.toString(data));        binaryInsertSort(data);                System.out.println("排序之后：" + Arrays.toString(data));    }    }
     

算法分析

折半插入排序降低了keyword的比較次数。可是记录的移动次数不变。其时间复杂度与直接插入排序同样。