二分插入排序是对二分查找和插入排序的一个结合，插入操作时通过二分查找找到要插入的位置.
~~~
#include <stdio.h>
// 打印数组a
void printArr(int a[],int n){
for (int i = 0; i < n; ++i)
{
printf("%d\t",a[i]);
}
printf("\n");
}
void ModInsertSort(int a[],int n){
int i,j,temp,left,right,mid;
for ( i = 1; i < n; ++i)
{
left=0;
temp=a[i];
right=i-1;
while(left<=right){
mid=(left+right)/2;
if(a[mid]>temp){
right=mid-1;
}else{
left=mid+1;
}
}
for ( j = i-1; j >right;j--)
a[j+1]=a[j];
a[right+1]=temp;
}
}
int main(){
int a1[]={10,111,22,31,14,57,46,89,39};
ModInsertSort(a1,9);
printArr(a1,9);
}
输出结果：
yaopans-MacBook-Pro:algorithm yaopan$ ./a.out
10 14 22 31 39 46 57 89 111
~~~
### JAVA描述
~~~
public class BinInserSort {
//二分插入排序
public static void ModInsertSort(int a[]){
int i,j,right,left,mid,temp;
for (i =1; i < a.length; ++i) {
temp=a[i];
left=0;
right=i-1;
while(left<=right){
mid=(left+right)/2;
if(a[mid]>temp){
right=mid-1;
}else{
left=mid+1;
}
}
for(j=i-1;j>right;j--){
a[j+1]=a[j];
}
a[right+1]=temp;
}
}
public static void printArry(int[] a){
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+"\t");
}
System.out.println("\n");
}
public static void main(String[] args) {
int a[]={1,2,34,24,5,6,7,8,77,90,37,19,20};
System.out.println("排序前:");
printArry(a);
ModInsertSort(a);
System.out.println("排序后:");
printArry(a);
}
}
排序前:
1 2 34 24 5 6 7 8 77 90 37 19 20
排序后:
1 2 5 6 7 8 19 20 24 34 37 77 90
~~~
