binaryinsertsort.h

改进的排序算法分析程序

template
< class T >
void BinaryInsertSort(T a[], int N, int& KCN, int& RMN)
{
	KCN = 0;
	RMN = 0;

	for (int i = 1; i < N; i++)
	{
		T temp = a[i];
		RMN++;

		int low = 0, high = i - 1;

		while (low <= high) //折半查找
		{
			int mid = (low + high) / 2;
			if (++KCN && temp < a[mid])
				high = mid - 1;
			else
				low = mid + 1;
		}

		for (int j = i - 1; j >= low; j--)
		{
			a[j + 1] = a[j];
			RMN++;
		} //记录后移

		a[low] = temp;
		RMN++; //插入
	}
}