计数排序

如果给一个分布于区间[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 }