二分（折半）插入排序是一种在直接插入排序算法上进行小改动的排序算法。其与直接排序算法最大的区别在于查找插入位置时使用的是二分查找的方式，在速度上有一定提升。

1. 原理解析

总共有N个元素，当插入第i个元素时，对前面的 0~i-1 个元素进行折半，先跟他们中间的那个元素比，如果小，那么再对前半折半 否则对后半进行折半，知道左<右，然后再把第i个元素前一位于目标位置之间的所有元素后移，再把第i个元素放在目标位置上。

关说原理可能大家不是很理解，下面我们就用一个列子来详细说明一下：
例如：我们当前数组为 [4 5 7 10 29 30] 11
已知当前 0到第N-1个 都是按顺序排序，现在对第N个11找对应位置。

1.1. 第一趟

• [4 5 7 10 29 30] 11
• L M R
• 11比中间M大

1.2. 那么接下来第二趟为：

• [4 5 7 10 29 30] 11
• L M R
• 11比中间M大
• 那么11的位置就在M+1这个

注意，我们这里的第0到第N-1已经是按照要求排好序的

public class BinarySort {

    public static void main(String[] args) {
            int ia[] = {2,4,5,1,9,8,7,6,3};
            sort(ia);
        System.out.println(Arrays.toString(ia));
    }

    public static void sort( int[] array) {
        for (int i = 1; i < array.length; i++) {
            int temp = array[i];
            int low = 0, high = i - 1;
            int mid = -1;
            while (low <= high) {
                mid = low + (high - low) / 2;
                if (array[mid] > temp) {
                    high = mid - 1;
                } else { // 元素相同时，也插入在后面的位置
                    low = mid + 1;
                }
            }
            System.out.println("i:"+i+" "+Arrays.toString(array));
            for(int j = i - 1; j >= low; j--) {
                array[j + 1] = array[j];
            }
            array[low] = temp;
            System.out.println("i:"+i+" "+Arrays.toString(array));
        }
    }
}

• 当前 i 为 8 值为 3
• 计算第一次: 从0开始 到 high - 1 的位置 0 7,7/2=3 i 的 3 为 5 此时判断 5 是大于还是小于 小于 查找 3 前面索引值,大于查找 3 后面的索引值
• 每次计算 low + (high - low) / 2 开始位置 + （高度-开始 / 2）