C语言实现折半插入排序算法

折半搜索有序子表找到待插入位置，然后移动元素腾出位置并插入

//每趟先找到插入位置，然后移动、插入 
void InsertSort2(int a[],int n){
	int i,j,low,high,mid,k;
	for(i=1;i<n;i++){//将a[1]~a[n-1]插入到前面已排序列 
		k=a[i];
		low=0;
		high=i-1;
		while(low<=high){//寻找插入位置 
			mid=(low+high)/2;
			if(a[mid]>k)
				high=mid-1;//查找左半子表
			else low=mid+1;//查找右半子表 
		}
		for(j=i-1;j>=high;j--){//后移，腾出插入位置 
			a[j+1]=a[j];
		}
		a[high+1]=k;//插入 
	}
}