算法介紹
計(jì)數(shù)排序是一個(gè)類(lèi)似于桶排序的排序算法，其優(yōu)勢(shì)是對(duì)已知數(shù)量范圍的數(shù)組進(jìn)行排序。它創(chuàng)建一個(gè)長(zhǎng)度為這個(gè)數(shù)據(jù)范圍的數(shù)組C，C中每個(gè)元素記錄要排序數(shù)組中對(duì)應(yīng)記錄的出現(xiàn)個(gè)數(shù)。這個(gè)算法于1954年由 Harold H. Seward 提出。
當(dāng)輸入的元素是 n 個(gè) 0 到 k 之間的整數(shù)時(shí)，它的運(yùn)行時(shí)間是 Θ(n + k)。計(jì)數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。
由于用來(lái)計(jì)數(shù)的數(shù)組C的長(zhǎng)度取決于待排序數(shù)組中數(shù)據(jù)的范圍（等于待排序數(shù)組的最大值與最小值的差加上1），這使得計(jì)數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組，需要大量時(shí)間和內(nèi)存。例如：計(jì)數(shù)排序是用來(lái)排序0到100之間的數(shù)字的最好的算法，但是它不適合按字母順序排序人名。但是，計(jì)數(shù)排序可以用在基數(shù)排序中的算法來(lái)排序數(shù)據(jù)范圍很大的數(shù)組。計(jì)數(shù)排序之所以能夠突破前面所述的Ω(nlgn)極限，是因?yàn)樗皇腔谠乇容^的。計(jì)數(shù)排序適合所需排序的數(shù)組元素取值范圍不大的情況(范圍太大的話輔助空間很大)。
定理：任意一個(gè)比較排序算法在最壞情況下，都需要做Ω(nlgn)次比較。
算法的步驟如下：
- 找出待排序的數(shù)組中最大和最小的元素
- 統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)
- 對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開(kāi)始，每一項(xiàng)和前一項(xiàng)相加）
- 反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1
以下引自麻省理工學(xué)院算法導(dǎo)論——筆記：
Counting sort: No comparisons between elements.
• Input: A[1 . . n], where A[ j]??{1, 2, …, k} .
• Output: B[1 . . n], sorted.
• Auxiliary storage: C[1 . . k] .
Counting sort
for i ← 1 to k
do C[i] ← 0
for j ←1 to n
do C[A[ j]] ← C[A[ j]] + 1 —> C[i] = |{key = i}|
for i ← 2 to k
do C[i] ← C[i] + C[i–1] —>C[i] = |{key ← i}|
for j ← n downto 1
do B[C[A[ j]]] ← A[ j]
C[A[ j]] ← C[A[ j]] – 1
實(shí)例：
對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開(kāi)始，每一項(xiàng)和前一項(xiàng)相加）
反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1
注：基于比較的排序算法的最佳平均時(shí)間復(fù)雜度為 O(nlogn)
穩(wěn)定性：算法是穩(wěn)定的。
如果k小于nlogn可以用計(jì)數(shù)排序，如果k大于nlogn可以用歸并排序。
代碼實(shí)例：
1 C++實(shí)現(xiàn)：
2 #include<cstdio>
3 #include<algorithm>
4 using namespace std;
5 //n為數(shù)組元素個(gè)數(shù)，k是最大的那個(gè)元素
6 void CountingSort(int *input, int size, int k){
7 int i;
8 int *result = new int[size]; //開(kāi)辟一個(gè)保存結(jié)果的臨時(shí)數(shù)組
9 int *count = new int[k+1]; //開(kāi)辟一個(gè)臨時(shí)數(shù)組
10 for(i=0; i<=k; ++i)
11 count[i]=0;
12 //使count[i]等于等于i的元素的個(gè)數(shù)
13 for(i=0; i<size; ++i)
14 ++count[input[i]]; //count數(shù)組中坐標(biāo)為元素input[i]的增加1，即該元素出現(xiàn)的次數(shù)加1
15 for(i=1; i<=k; ++i)
16 count[i] += count[i-1];
17 for(i=size-1; i>=0; --i){ //正序來(lái)也行，但是到這來(lái)可以使排序是穩(wěn)定的
18 --count[input[i]]; //因?yàn)閿?shù)組下標(biāo)從0開(kāi)始，所以這個(gè)放在前面
19 result[count[input[i]]] = input[i]; //這個(gè)比較繞， count[input[i]-1] 就代表小于等于元素
}
20 copy(result,result+size,input); //調(diào)用copy函數(shù)把結(jié)果存回原數(shù)組
21 delete [] result; //記得釋放空間
22 delete [] count;
23 }
24 int main()
25 {
26 int input[11]={2,7,4,9,8,5,7,8,2,0,7};
27 CountingSort(input,11,9);
28 for(int i=0; i<11; ++i)
29 printf("%d ",input[i]);
30 putchar('\n');
31 return 0;
32 }
posted on 2012-11-13 11:07
王海光 閱讀(721)
評(píng)論(1) 編輯 收藏 引用 所屬分類(lèi):
算法