经典算法之折半插入排序（Binary Insertion Sort）

认定array[0]为有序区，其余部分为无序区，同时令 i = 1；
将array[i]与有序区中的中间元素比较，同时通过折半查找找到插入的位置插入；
重复上述操作，直到元素全部插入完成。
public class Sort {
    public static void main(String[] args) {
        // 待排序的数组
        int[] array = {15,2,6,54,36,1,0,13,-5,68,79};
        binaryInsertSort(array);
        // 显示排序后的结果。
        System.out.print("排序后： ");
        for(int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }
    static void binaryInsertSort(int[] array) {
        for(int i = 1; i < array.length; i++) {
            int temp = array[i];
            int low = 0;
            int high = i - 1;
            //折半查找
            while(low <= high) {
                //取中间点
                int mid = (low + high) / 2;
                if(temp < array[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            for(int j = i; j >= low + 1; j--) {
                array[j] = array[j - 1];
            }
            array[low] = temp;
        }
    }
}