基本思路：折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。
步骤：
（1） 将一新的元素插入到有序数组中，寻找插入点时，将带插区域的首元素设置为a[low],末元素设置为a[high],比较时则将待插元素与参考元素a[m]（m=(low+high)/2）相比较。；
（2）如果待插元素比参考元素小，则选择a[low]到a[m-1]为新的插入区域（即high=m-1）,否则选择a[m+1]到a[high]为插入区域；
（3）如此直到low<=high不成立，即将此位置(low)之后所有元素后移一位，并将新元素插入a[high+1]中。
代码如下：
public class Binary_Insert_Sort {
public static void main(String[] args){
int[] a = {1,3,2,5,4,4,4,4,4,4,5,5,5,5,5,5,5,1,1,1,1,2,2,2,3,4,5,7,3,2,2,24,54};
long start = System.nanoTime();
sort(a);
long end = System.nanoTime();
System.out.println(end-start + " " + Arrays.toString(a));
}
////程序运行时间：14639ms
public static void sort(int[] s){
for(int i = 1; i < s.length; i++){
int temp = s[i];//待插元素
int low = 0;
int high = i-1;
while(low<=high){
int mid = (low+high)/2;
if(temp>s[mid]){//待插元素比中间值大,取m+1到high区域
low = mid+1;
}else{
high= mid-1;
}
}
for(int j = i;j>low;j--){//将low后面的数组整体后移
s[j]=s[j-1];
}
s[low]=temp;
}
}
}
