计数排序
Chipset发表于 2011-08-16 05:58:00
计数排序
如果给一个分布于区间[min, max)的随机序列排序，可以考虑使用计数排序，max-min 越小说明分布越集中，此时使用计数排序效果就越好，计数排序是一种稳定的排序算法。一般而言，计数排序的时间复杂度为O(n)，空间复杂度O(n)，从理论上来看，它比时间复杂度O(nlogn)的算法明显快一些。
使用计数排序算法对一个正整数序列进行升序排序时，假设对于某个元素比它小的元素个数为 i(其中0≤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 }
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 }