統計排序

統計排序是一個非基於比較的線性時間排序算法。它對輸入的數據有附加的限制條件：
1、輸入的線性表的元素屬於有限偏序集S；
2、設輸入的線性表的長度為n，|S|=k（表示集合S中元素的總數目為k），則k=O(n)。
在這兩個條件下，統計排序的複雜性為O(n)。
統計排序算法的基本思想是對於給定的輸入序列中的每一個元素x，確定該序列中值小於x的元素的個數。一旦有了這個信息，就可以將x直接存放到最終的輸出序列的正確位置上。例如，如果輸入序列中只有17個元素的值小於x的值，則x可以直接存放在輸出序列的第18個位置上。當然，如果有多個元素具有相同的值時，我們不能將這些元素放在輸出序列的同一個位置上，因此，上述方案還要作適當的修改。
假設輸入的線性表L的長度為n，L=L1,L2,..,Ln；線性表的元素屬於有限偏序集S，|S|=k且k=O(n)，S={S1,S2,..Sk}；則統計排序算法可以描述如下：
掃描整個集合S，對每一個Si∈S，找到線上性表L中小於等於Si的元素的個數T(Si)；
掃描整個線性表L，對L中的每一個元素Li，將Li放在輸出線性表的第T(Li)個位置上，並將T(Li)減1。
具體的實現如下：
void Counting_Sort(int a[], int b[], int l, int k)
...{
int* c = new int[k];
memset(c, 0, k * sizeof(int));
for (int j = 0; j < l; j++) c&#91;a&#91;j&#93;&#93;++;
for (int j = 1; j < k; j++) c&#91;j&#93; += c&#91;j - 1&#93;;
for (int j = l - 1; j >= 0; j--)
...{
b&#91;c&#91;a&#91;j&#93;&#93; - 1&#93; = a&#91;j&#93;;
c&#91;a&#91;j&#93;&#93;--;
}
delete &#91;&#93;c;
}
其中a為輸入，b為輸出，l為元素個數，k為元素最大值。
我們看到，統計排序算法沒有用到元素間的比較，它利用元素的實際值來確定它們在輸出數組中的位置。因此，統計排序算法不是一個基於比較的排序算法，從而它的計算時間下界不再是Ω(nlogn)。另一方面，統計排序算法之所以能取得線性計算時間的上界是因為對元素的取值範圍作了一定限制，即k=O(n)。如果k=n2,n3,..，就得不到線性時間的上界。此外，我們還看到，由於算法第4行使用了downto語句，經統計排序，輸出序列中值相同的元素之間的相對次序與他們在輸入序列中的相對次序相同，換句話說，統計排序算法是一個穩定的排序算法。