//計數(shù)排序
//說明：
不同與比較排序算法，計數(shù)排序算法不涉及到數(shù)據(jù)元素間的比較。
計數(shù)排序適用于小范圍集中的數(shù)據(jù)的排序，它以空間換取時間，能達到線性的時間復(fù)雜度。
計數(shù)排序關(guān)鍵一點是：對于每一個元素x，確定有多少個元素不大于它---假設(shè)有n個元素小于或等于x（包括了x），則把x放在位序為n的地方即可。
實際中，此算法很可能沒快排和堆排好。

//算法思想：
{線性表}
1。假設(shè)原始數(shù)據(jù)為ListA，數(shù)據(jù)的范圍從0到k。
2。產(chǎn)生新的線性表ListC[0..k]，即刻度表。
3。把ListC[0..k]各元素值置為0，即刻度值均為0。
4。遍歷ListA，對于每一個元素j=ListA[i]，0<=j<=k。設(shè)ListC[j]=ListC[j]+1。
5。當(dāng)m=1 到 m=k 時，依次執(zhí)行 ListC[m] = ListC[m]+ListC[m-1]。
6。產(chǎn)生新的線性表ListB[1..Length(ListA)]，用來存放最終排序的結(jié)果。
7。當(dāng)n=Length(ListA)到n=1時，執(zhí)行如下操作：
8。ListB[ListC[ListA[n]]]=ListA[n]。
9。ListC[ListA[n]] = ListC[ListA[n]] - 1。轉(zhuǎn)至步驟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}

//時間復(fù)雜度
O(n)

//代碼實現(xià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;
}