二分排序法

二分排序法，实际上是二分查找法+直接插入排序法的灵活组合。

先来看看二分查找法，二分查找法的前提是给出的队列是有序的，通过不断的折半查找，找到指定key对应的数组位置。

//二分查找法
public static int BinarySearch(int[] list, int key) {
    int mid = (list.length - 1) / 2;
    if (list[mid] == key) {
        return mid;
    }

    int left = 0;
    int right = list.length - 1;
    
    //while条件是小于等于
    while (left <= right) {
        //勿漏加left，没有加left，当key在折半右边时，会出错
        mid = (right - left) / 2 + left;
        if (key > list[mid]) {
            left = mid + 1;
        } else if (key < list[mid]) {
            right = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

我们再来看看直接插入法

//直接插入排序法
public static void insertSort(int[] list) {
    int temp;
    int j;
    for (int i=0; i<list.length; i++) {
        temp = list[i];

        for (j=i-1; j>=0 && list[j]>temp; j--) {
            list[j+1] = list[j];
        }
        //注意：temp赋值给j+1，不是j。for循环特性
        list[j+1] = temp;
    }
}

直接插入法的最大特点是在第i个数之前的数组都是有序的，我们可以利用二分查找法提高直接插入排序的效率

//二分查找排序法
public static void binaryInsertSort(int[] list) {
    int temp, j, mid;
    for (int i=0; i<list.length; i++) {
        temp = list[i];
        //把temp当成key，利用二分查找法，找到temp需要插入的位置
        int left = 0;
        int right = i - 1; //取i之前的数组

        while (left <= right) {
            mid = (right - left)/2 + left;

            if (temp > list[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        //通过二分查找法找到temp需要插入的位置left。
        for(j=i-1; j>=left; j--) {
            list[j+1] = list[j];
        }
        //把temp 赋值给left的位置
        list[left] = temp;
    }
}