折半插入排序（BInsertSort）

折半插入排序的特点和折半插入排序的完整实现代码。

折半插入排序

特点

折半查找找到应插入的位置，仅适用于顺序表。时间复杂度O(n^2)，并没有比插入排序快多少。

注意：一直到low>high时才停止折半查找。当mid所指元素等于当前元素时，应继续令low = mid +1,以保证“稳定性”。最终应将当前元素插入到low所指位置（即high+1）

完整实现代码

#include<iostream>
#include<string>

using namespace std;

/* 折半插入排序 */
void BInsertSort(int A[],int len)
{
	int i, j, low, mid, high;
	for (i = 2; i <= len; i++)//依次将A[2]~A[n]插入前面的已排序序列
	{
		A[0] = A[i];//将A[i]暂存到A[0]
		low = 1; //设置折半查找的范围
		high = i - 1;
		while (low<=high)//折半查找（默认递增有序）
		{
			mid = (low + high) / 2;//取中间点
			if (A[mid]>A[0])
			{
				high = mid - 1;//查找左半子表
			}
			else
			{
				low = mid + 1;//查找右半子表
			}
		}
		for (j = i-1; j >= high+1; --j)
		{
			A[j + 1] = A[j]; //统一后移元素，空出插入位置
		}
		A[high + 1] = A[0];//插入操作
	}
}

int main()
{
	//哨兵是用来判断程序何时结束的
	//有暂存单元的数组，第一个是暂存单元
	int A[] = {0,3,5,2,6,1,4,9,8 };
	BInsertSort(A, 8);
	cout << "折半插入排序后：" << endl;
	for (int i = 1; i <= 8; i++)
	{
		cout << A[i];
		if (i == 8)
		{
			cout <<endl;;
		}
		else
		{
			cout << ",";
		}
	}
	system("pause");
	return 1;
}