coutingsort.h

来自「比快速排序更快的排序算法；这个了示例包含多种数据结构的算法」· C头文件 代码 · 共 51 行

template
< class T >
void CoutingSort(T a[], int N, int& KCN, int& RMN)
{
	int k = 0;
	for ( int i = 0;i < N;i++ )
	{
		if ( ++KCN && a[i] > k )
		{
			k = a[i];
			RMN++;
		}
	}
	
	int *c = new int[k + 1];
	int *b = new int[N];
	for ( int j = 0;j <= k;j++ )
	{
		c[j] = 0;
	}
	
	//After this, in array c,c[i] is the times of i appears in array a
	for ( i = 0;i < N;i++ )
	{
		c[ a[i] ]++;
	}
	//After this,in array c, c[i] is the times of n(n<=i) appears in array a
	for ( i = 1;i <= k;i++ )
	{
		c[i] += c[ i - 1 ];
		RMN++;
	}
	
	//this is the most powerful part of the algorithm
	for ( i = N - 1;i >= 0;i-- )
	{
		b[ c[a[i]] - 1 ] = a[i];
		RMN++;
		c[ a[i] ]--;
	}
	for ( i = 0;i < N;i++ )
	{
		a[i] = b[i];
		RMN++;
	}
	
	delete c;
	c = NULL;
	delete b;
	b = NULL;
}