一、折半插入排序（二分插入排序）
一般在A[k]和A[r]之间採用折半。当中间结点为A[k+r/2]。经过一次比較就可以排除一半纪录，把可能插入的区间减小了一半，故称为折半。运行折半插入排序的前提是文件纪录必须按顺序存储。
二、算法原理
public class BinarySort {
public static void binarySort(int[] source) {
int i, j;
int high, low, mid;
int temp;
for (i = 1; i < source.length; i++) {
// 查找区上界
low = 0;
// 查找区下界
high = i - 1;
//将当前待插入记录保存在暂时变量中
temp = source[i];
while (low <= high) {
// 找出中间值
// mid = (low + high) / 2;
mid = (low + high) >> 1;
//假设待插入记录比中间记录小
if (temp<source[mid] ) {
// 插入点在低半区
high = mid - 1;
} else {
// 插入点在高半区
low = mid + 1;
}
}
//将前面全部大于当前待插入记录的记录后移
for (j = i - 1; j >=low; j--) {
source[j + 1] = source[j];
}
//将待插入记录回填到正确位置.
source[low] = temp;
System.out.print("第" + i + "趟排序：");
printArray(source);
}
}
private static void printArray(int[] source) {
for (int i = 0; i < source.length; i++) {
System.out.print("\t" + source[i]);
}
System.out.println();
}
public static void main(String[] args) {
int source[] = new int[] { 12, 15, 9, 14, 4, 18, 23, 6 };
System.out.print("初始keyword：");
printArray(source);
System.out.println("");
binarySort(source);
System.out.print("\n\n排序后结果：");
printArray(source);
}
}
四、执行结果：初始keyword： 12 15 9 14 4 18 23 6 第1趟排序： 12 15 9 14 4 18 23 6 第2趟排序： 9 12 15 14 4 18 23 6 第3趟排序： 9 12 14 15 4 18 23 6 第4趟排序： 4 9 12 14 15 18 23 6 第5趟排序： 4 9 12 14 15 18 23 6 第6趟排序： 4 9 12 14 15 18 23 6 第7趟排序： 4 6 9 12 14 15 18 23 排序后结果： 4 6 9 12 14 15 18 23
==================================================================================================
作者：欧阳鹏 欢迎转载，与人分享是进步的源泉！
转载请保留原文地址：http://blog.csdn.net/ouyang_peng
==================================================================================================
版权声明：本文欧阳鹏原创文章，欢迎转载，转载请注明出处http://blog.csdn.net/ouyang_peng
矿Java开发学习之旅------>Java排序算法经典的二分法插入排序
原文：http://www.cnblogs.com/gcczhongduan/p/4856681.html