tableinsertsort.h

改进的排序算法分析程序

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

	int* link = new int[N];
	int head = 0, pre, cur, i;
	link[0] = -1;

	for (i = 1; i < N; i++)
	{
		if (a[head] > a[i])
		{
			link[i] = head;
			head = i;
			KCN++;
		} //没设表头，因此需要此判断，失败时此次判断没记入KCN
		else
		{
			for (cur = head; cur != -1 && ++KCN && a[cur] <= a[i]; cur = link[cur])
				pre = cur;
			link[pre] = i;
			link[i] = cur;
		}
	}

	cur = head; //重排序列

	for (i = 0; i < N; i++)
	{
		while (cur < i)
			cur = link[cur];

		pre = link[cur];

		if (cur != i)
		{
			swap(a[i], a[cur]);
			RMN += 3;
			link[cur] = link[i];
			link[i] = cur;
		}

		cur = pre;
	}

	delete []link;
}