計(jì)數(shù)排序

如果給一個(gè)分布于區(qū)間[min, max)的隨機(jī)序列排序，可以考慮使用計(jì)數(shù)排序，max-min 越小說(shuō)明分布越集中，此時(shí)使用計(jì)數(shù)排序效果就越好，計(jì)數(shù)排序是一種穩(wěn)定的排序算法。一般而言，計(jì)數(shù)排序的時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度O(n)，從理論上來(lái)看，它比時(shí)間復(fù)雜度O(nlogn)的算法明顯快一些。

 使用計(jì)數(shù)排序算法對(duì)一個(gè)正整數(shù)序列進(jìn)行升序排序時(shí)，假設(shè)對(duì)于某個(gè)元素比它小的元素個(gè)數(shù)為 i(其中0≤i<max，獲取該信息無(wú)需借助比較運(yùn)算)，則排序后該元素就應(yīng)該位于數(shù)組下標(biāo)為i的位置。現(xiàn)在的問(wèn)題是，如果對(duì)于等于某個(gè)值的正整數(shù)不止一個(gè)該如何確定各自位置呢？這個(gè)問(wèn)題在實(shí)現(xiàn)中容易解決。

 為了能夠正常排序，需要用max-min 個(gè)輔助空間記錄不同正整數(shù)的個(gè)數(shù)，由于排序無(wú)法原地進(jìn)行，還需要開(kāi)辟等大的輔助空間容納排序后的所有正整數(shù)，一般而言，max-min 不大于待排序的正整數(shù)個(gè)數(shù)或與之相當(dāng)，可見(jiàn)空間復(fù)雜度為O(n + (max-min)) = O(n)。

以一個(gè)隨機(jī)整數(shù)序列為例，計(jì)數(shù)排序過(guò)程如下。

13 11 13 11 13 12 15 17 15

待排序序列

0    1    2    3    4    5    6    7    8

計(jì)數(shù)數(shù)組下標(biāo)

1    2    1    4    0    5    1    1    1

依次計(jì)數(shù)

1    3    4    8    8    13 14 15 16

計(jì)數(shù)累計(jì)

10 11 11 12 13 13 13 13 15

根據(jù)累計(jì)歸位

 1 #include <vector>
 2 template <typename ForwardIter>
 3 const ForwardIter max_element(ForwardIter first, ForwardIter last)
 4 {
 5   ForwardIter it = first;
 6   while(++first != last)
 7   {
 8     if(*it < *first)
 9       it = first;
10   }
11   return it;
12 }
13 
14 template <typename ForwardIter>
15 const ForwardIter min_element(ForwardIter first, ForwardIter last)
16 {
17   ForwardIter it = first;
18   while(++first != last)
19   {
20     if(*first < *it)
21       it = first;
22   }
23   return it;
24 }
25 // not portable implementation
26 void counting_sort(std::vector<unsigned long>& s)
27 {
28   if(s.empty() || 1 == s.size())
29     return;
30   typedef std::vector<unsigned long>::value_type value_type;
31   value_type max = *max_element(s.begin(), s.end());
32   value_type min = *min_element(s.begin(), s.end());
33   typedef std::vector<unsigned long>::size_type size_type;
34   std::vector<unsigned long> h(max - min + 1), d(s.size());
35   for(size_type i = 0; i < s.size(); ++i)
36     ++h[s[i]-min];
37   for(size_type i = 1; i < h.size(); ++i)
38     h[i] += h[i-1];
39   for(size_type i = 0; i < s.size(); ++i)
40     d[--h[s[i]-min]] = s[i];
41   s.swap(d);
42 }