quicksort.h

改进的排序算法分析程序

template
< class T >
int Partition(T a[], int left, int right, int& KCN, int& RMN)
{
	int pivotpos = left;
	T pivot = a[left]; //枢轴

	for (int i = left + 1; i <= right; i++)
		if (++KCN && a[i] < pivot && ++pivotpos != i)
		{
			swap(a[i], a[pivotpos]);
			RMN += 3;
		}

	swap(a[left], a[pivotpos]);
	RMN += 3;

	return pivotpos;
}

template
< class T >
void QSRecurve(T a[], int left, int right, int& KCN, int& RMN)
{
	if (left < right)
	{
		int pivotpos = Partition < T > (a, left, right, KCN, RMN);
		QSRecurve < T > (a, left, pivotpos - 1, KCN, RMN);
		QSRecurve < T > (a, pivotpos + 1, right, KCN, RMN);
	}
}

template
< class T >
void QuickSort(T a[], int N, int& KCN, int& RMN)
{
	KCN = 0;
	RMN = 0;
	QSRecurve < T > (a, 0, N - 1, KCN, RMN);
}