什么是計數(shù)排序

計數(shù)排序假設(shè)n個輸入元素中的每一個都是介于0到k之間的整數(shù)，此處k為某個整數(shù)。

計數(shù)排序的基本思想就是對每一個輸入元素x，確定出小于x的元素個數(shù)。有了這一信息，就可以把x直接放到它在最終輸出數(shù)組中的位置上。例如，如果有17個元素小于x，則x就屬于第18個輸出位置。當有幾個元素相同時，這個方案要略作修改，因為不能把它們放在同一個輸出位置上。

在計數(shù)排序算法的代碼中，我們假定輸入是個數(shù)組A[1...n]，另外還需要兩個數(shù)組：存放排序結(jié)果的B[1...n]，以及提供臨時存儲區(qū)的C[0...k]。

#includeusing?namespace?std;

#define?len?8

void?CountSort(int?A[],?int?B[],?int?k)
{
	int?*C=new?int[k+1];
	for(int?i=0;?i<=k;?i++)
		C[i]=0;

	//C[i]包含等于i的元素個數(shù)
	for(i=0;?i<len;?i++)
		C[A[i]]++;

	//C[i]包含小于等于i的元素個數(shù)
	for(i=1;?i=0;?i--)//從后往前處理A中的元素，以保證穩(wěn)定性
	{
		B[C[A[i]]-1]=A[i];//C[A[i]]表示A[i]在B中的位置，但B[i]從0開始，不是從1開始，所以要減1
		C[A[i]]--;//可處理元素重復問題

	}
}

void?main()
{
	int?a[len]={2,5,3,0,2,3,0,3};
	int?*b=new?int[len];
	CountSort(a,?b,?5);

	for(int?i=0;?i<len;?i++)
		cout<<b[i]<<"?";
	cout<<endl;

}

計數(shù)排序運行時間O(n)，計數(shù)排序不是基于比較的排序算法。

計數(shù)排序的一個重要性質(zhì)就是它是穩(wěn)定的：具有相同值的元素在輸出數(shù)組中的相對次序與它們在輸入數(shù)組中的次序相同。亦即，兩個相同數(shù)之間的順序是這樣來規(guī)定的，即在輸入數(shù)組中先出現(xiàn)的，在輸出數(shù)組中也位于前面。之所以說計數(shù)排序的穩(wěn)定性非常重要，是因為計數(shù)排序經(jīng)常用作基數(shù)排序算法的一個子過程。計數(shù)排序的穩(wěn)定性對基數(shù)排序的正確性來說，是非常關(guān)鍵的。

保證計數(shù)排序穩(wěn)定的重要語句是：for(i=len-1; i>=0; i--)//從后往前處理A中的元素，以保證穩(wěn)定性。

?

?

?