折半插入排序

#include<stdio.h>
//折半插入排序
/*算法思想：从前面已排好序的序列中，取一个中间元素，把这个中间元素
与当前要插入的元素相比较；如果中间元素比当前元素大，则要从
中间元素前面的序列中重新选取一个新的中间元素，如果中间元素比当前元素小，则要从
中间元素后面的序列中重新选取一个新的中间元素，直到找出当前元素要插入的位置；
然后统一后移元素，空出插入位置；最后插入当前元素。*/
void binaryInsertSort(int *arr, int n)
{
	int i, j, low, high, mid, t;
	for (i = 1; i < n; i++)
	{
		t = arr[i];
		low = 0, high = i - 1;
		while (low <= high)//要用<=而不能只<，low==high表示前面有一个元素
		{
			mid = (low + high) / 2;//从前面已排好序的序列中取中间点
			if (arr[mid] > t)
				high = mid - 1;
			else
				low = mid + 1;
		}
		for (j = i - 1; j >= high + 1; j--)
			arr[j + 1] = arr[j];          //统一后移元素，空出插入位置
		arr[high + 1] = t;                //插入操作
	}
}
int main()
{
	int arr[10] = { 6,4,7,3,9,1,2,5,8,0 }, i;
	binaryInsertSort(arr, 10);
	for (i = 0; i < 10; i++)
		printf("%d ", arr[i]);
	return 0;
}