計數排序

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

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

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

以一個隨機整數序列為例，計數排序過程如下。

13 11 13 11 13 12 15 17 15

待排序序列

0    1    2    3    4    5    6    7    8

計數數組下標

1    2    1    4    0    5    1    1    1

依次計數

1    3    4    8    8    13 14 15 16

計數累計

10 11 11 12 13 13 13 13 15

根據累計歸位

 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 }