计数排序.txt

计数排序的算法描述

//计数排序
//说明：
不同与比较排序算法，计数排序算法不涉及到数据元素间的比较。
计数排序适用于小范围集中的数据的排序，它以空间换取时间，能达到线性的时间复杂度。
计数排序关键一点是：对于每一个元素x，确定有多少个元素不大于它---假设有n个元素小于或等于x（包括了x），则把x放在位序为n的地方即可。
实际中，此算法很可能没快排和堆排好。

//算法思想：
{线性表}
1。假设原始数据为ListA，数据的范围从0到k。
2。产生新的线性表ListC[0..k]，即刻度表。
3。把ListC[0..k]各元素值置为0，即刻度值均为0。
4。遍历ListA，对于每一个元素j=ListA[i]，0<=j<=k。设ListC[j]=ListC[j]+1。
5。当m=1 到 m=k 时，依次执行 ListC[m] = ListC[m]+ListC[m-1]。
6。产生新的线性表ListB[1..Length(ListA)]，用来存放最终排序的结果。
7。当n=Length(ListA)到n=1时，执行如下操作：
8。ListB[ListC[ListA[n]]]=ListA[n]。
9。ListC[ListA[n]] = ListC[ListA[n]] - 1。转至步骤7。

//算法描述
{顺序存储}
CountingSort(ListA, ListB, k)
	ListC[0...k] = CreateList();
	for p=0 to k
	[
		List[p] = 0;
	]
	for j=1 to Length(ListA)
	[
		ListC[ListA[j]] = ListC[ListA[j]] + 1;		
	]
	for m=1 to k
	[
		ListC[m] = ListC[m] + ListC[m-1];
	]
	for n=Length(A) downto 1
	[
		ListB[ListC[ListA[n]]] = ListA[n];
		ListC[ListA[n]] = ListC[ListA[n]] - 1;
	]
{CountingSort end}

//时间复杂度
O(n)

//代码实现
void	CountingSort( 
					 int ListA[],
					 int nListALen,
					 int ListB[], 
					 int  nMaxValue
					 )
{
	int * pListC = new int[nMaxValue+1]; // 空间换时间(如果nMaxValue很大是不可行的)
	
	for ( int nPos = 0; nPos < nMaxValue+1; nPos ++ )
		pListC[nPos] = 0;

	for ( int nPos = 0; nPos < nListALen; nPos ++ )
		pListC[ListA[nPos]] ++;

	for ( int nPos = 1; nPos < nMaxValue+1; nPos ++ )
		pListC[nPos] += pListC[nPos-1];

	for ( int nPos = nListALen-1; nPos >= 0; nPos -- )
	{
		ListB[pListC[ListA[nPos]]-1] = ListA[nPos];
		pListC[ ListA[nPos] ] --;
	}

	delete [] pListC;
	pListC = NULL;
}

//测试代码
void	testCountingSort()
{
	const int Len = 13;
	int  ListA[Len] = {1, 45, 23, 78, 69, 54, 10, 25, 100, 123, 256, 45, 1 };
	int  ListB[Len];
	CountingSort( ListA, Len, ListB, 256 );

	for ( int nPos = 0; nPos < Len; nPos ++ )
		cout << ListB[nPos] << " ";
	cout << endl;
}