排序算法（三）折半插入排序算法
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)。
