折半插入排序

1.排序原理

利用折半查找的方法来查找插入的位置，然后再直接将需要插入的数据插入该位置即可

<mark>排序过程</mark>

以从小到大排序为例，首先用key存储需要排序的数据
第一步：折半查找——用low、mid、high划分两个区域【low，mid-1】和【mid+1，high】
第二步：判断——如果key值小于序列的中间值【mid】，则代表key值应该插入左边的区域【low，mid-1】，然后对【low，mid-1】再重复划分区域，直到low>high为止
第三步：插入——最后的插入位置应该是high+1，我们只需要先将high之后位置的数据整体后移，然后将key赋值给【mid+1】，即完成插入。

<mark>如图</mark>

2.源代码：

#include<stdio.h>
void BInsertSort(int num[],int N)
{
	int i,j,low,high,mid,key;
	for(i=1;i<=N;i++)
	{
		key=num[i];
		low=0;
		high=i-1;
		while(low<=high)//折半查找
		{
			mid=(low+high)/2;
			if(num[mid]>key)
				high=mid-1;//如果大于key值，则查找范围缩小到左子序列
			else
				low=mid+1;//如果小于key值，则查找范围缩小到右子序列
		}
		for(j=i-1;j>=high+1;j--)
			num[j+1]=num[j];//将high之后的数据整体后移
		num[high+1]=key;//将key值插入该位置
	}
}
int main()
{
	int num[10]={9,8,7,6,5,4,3,2,1,0};
	BInsertSort(num,10);
	for(int i=0;i<10;i++)
		printf("%d ",num[i]);
	printf("\n");
	return 0;
}