插入排序------折半插入排序

折半插入思路：

        在插入A[i]时，A[0]，A[1]，······A[i-1]已经按排序码升序排好了，在A[k]和A[r]之间采用折半，中间结点为A[k+(r-k)/2]。

        折半：经过一次比较，可以排除一半的记录。把可能插入的区间减少了一半。

        时间复杂度：。进行遍历的数量级是n，进行比较的数量级是。

#include<stdio.h>
#include<assert.h>
typedef int ElemType;
struct ForSort
{
	ElemType elem;
};

void BinaryInsertionSort(ForSort *arr,int n)
{
	assert(arr != NULL);
	assert(n > 0);

	int i, k, r;
	ForSort temp;
	for (i = 1; i < n; ++i)
	{

		temp = arr[i];
		k = 0;
		r = i - 1;
		while (k <= r)	//区域左右下标：相遇或者错过
		{
			int m;
			m = k + (r - k) / 2;	/*中间坐标*/
			if(temp.elem<arr[m].elem)
			{
				r = m - 1;		/*在前半部分继续找插入位置*/
			}
			else
			{
				k = m + 1;		/*在后半部分继续找插入位置*/
			}
		}
		
		/*找到了插入位置k*/
		for (r = i; r > k; r--)
		{
			arr[r] = arr[r - 1];
		}
		arr[k] = temp;
	}
}

int main()
{
	ForSort arr[] = { 98,78,76,65,54,32,12 };
	int n = sizeof(arr) / sizeof(ForSort);
	BinaryInsertionSort(arr, n);
	for (int i = 0; i < n; i++)
		printf("%-4d", arr[i].elem);
	return 0;
}

本程序在VS2017下运行通过