排序算法（三）折半插入排序算法

1.基本概念
  折半插入排序（Binary-Insertion-Sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。

2.算法思路
因为在一个有序序列中查找一个插入位置，所以可使用二分查找，减少元素比较次数提高效率。
  1.先取出预插入的数，通过二分查找法找到插入位置（insert_index）。
  2.再进行插入排序，直到预插入数插入到插入位置（insert_index）即可。
  重复1、2步，直到遍历完所有数。

3.代码实现

    private void binaryInsertionSort() {
        int[] numbers = {54, 32, 66, 8, 1, 6, 77, 69, 19};
        for (int i = 1; i < numbers.length; i++) {
            // 获取插入位置
            int insert_index = binarySearch(numbers, i, numbers[i]);
            // 当 insert_index = -1 时，不必做插入操作
            if (insert_index != -1) {
                // 一下是插入排序
                int temp = numbers[i];
                int j = i - 1;
                while (j >= insert_index) {
                    numbers[j + 1] = numbers[j];
                    j--;
                }
                numbers[j + 1] = temp;
            }
        }
    }

    /**
     * 二分查找法
     * @param numbers 数据数组
     * @param n 预插入数再数组中的下标
     * @param value 预插入数
     * @return 插入位置，找不到插入位置时返回-1，说明预插入数已经与之前的数列形成有序序列
     */
    private int binarySearch(int[] numbers, int n, int value) {
        int left = 0;
        int right = n - 1;
        while (left <= right) {
            int middle = (left + right) /2;
            if (value <= numbers[middle]) {
                right = middle - 1;
            } else if (value > numbers[middle]) {
                left = middle + 1;
            }
        }
        // 当 left >= n 时，则说明预插入数与其之前的有序序列
        // 已经形成有序序列了，因此不需要做插入操作
        return (left < n) ? left : -1;
    }

4.总结
  折半插入排序算法是一种稳定的排序算法，比直接插入算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，折半查找只是减少了比较次数，但是元素的移动次数不变，所以算法的时间复杂度仍然为O(n^2)。