折半插入排序
一、基本概念
当直接插入排序进行到某一趟时，对于 r[i].key 来讲，前边 i-1 个记录已经按关键字有序。此时不用直接插入排序的方法，而改为折半查找，找出 r[i].key 应插的位置，然后插入。这种方法就是折半插入排序（ Binary insertion sort ）。
二、具体操作
在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为a[low]，末元素设置为a[high]，则轮比较时将待插入元素与a[m]，其中m=(low+high)/2相比较,如果比参考元素大，则选择a[low]到a[m-1]为新的插入区域(即high=m-1)，否则选择a[m+1]到a[high]为新的插入区域（即low=m+1），如此直至low<=high不成立，即将此位置之后所有元素后移一位，并将新元素插入a[high+1]。
三、稳定性及复杂度
折半插入排序算法是一种稳定的排序算法，比直接插入算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，关键字的比较次数由于采用了折半查找而减少，数量级为Ｏ(nlog 2n) ，但记录移动的次数没有变，所以折半插入排序算法的时间复杂度仍然为O(n^2)，与直接插入排序算法相同。附加空间O(1)。
四、示例代码：
public class ZhebanCharuPaixu {
public static void main(String[] args) {
// 待排序的数组
int[] array = { 1, 0, 5, 3, 9, 10, 6, 7 };
binaryInsertSort(array);
// 显示排序后的结果
System.out.print("排序后： ");
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + "->");
}
}
private static void binaryInsertSort(int[] array) {
if(array.length == 0){
return;
}
for (int i = 1; i < array.length; i++) {
int temp = array[i];
int low = 0;
int high = i - 1;
while (low <= high) {
// int mid = (high - low) / 2 + low;
// 下面这样可能会有整型溢出的问题
int mid = (low + high) / 2;
if (temp < array[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
// 下面的for循环中，有人用 j > mid; 还有人用 j >= high + 1，这个还需要再看看
for (int j = i; j >= low + 1; j--) {
array[j] = array[j - 1];
}
array[low] = temp; // 此处用 array[high+1] = temp; 也可
}
}
}