算法导论第三版--桶排序

理解了基数排序，也就理解了桶排序。

桶排序就是基数排序的一种优化，从MSD开始，即取最高位来排一次序，如果最高位没有重复（意味着没有冲突需要处理），是算法的最佳状态，O（n）。

如果有冲突，就将冲突的元素存放到对应的桶里（代码就是一个链表或者数组或者stl容器），然后对每个桶进行一次插入排序，平均情况的话冲突很小的，桶里的元素的数量就不多，速度很快，

如果冲突集中在几个桶甚至一个桶里，那么就出现了算法的最差情形，也就是O(n^2)的复杂度。

下面是例子代码实现：

 1 template<typename _InIt>
 2 void bucket_sort(_InIt first, _InIt last, short decimal_bits) {
 3     typedef typename iterator_traits<_InIt>::value_type _ValueType;
 4     typedef typename vector<_ValueType>::iterator _Iterator;
 5 
 6     int n = last - first;
 7     if (n <= 0) return;
 8 
 9     vector< vector<_ValueType> > v(n, vector<_ValueType>());
10     _InIt it = first;
11     for(; it!=last; ++it) {
12         int i = bucket_index(*it, decimal_bits);
13         v[i].insert(v[i].begin(), *it);
14     }
15 
16     typename vector< vector<_ValueType> >::iterator ite = v.begin();
17     less_equal<_ValueType> cmp;
18     it = first;
19 
20     for(; ite!=v.end(); ++ite) {
21         if (ite->empty()) continue;
22         insert_sort(ite->begin(), ite->end(), cmp);
23         for(_Iterator _it=ite->begin(); _it!=ite->end(); ++_it)
24             *it++ = *_it;
25     }
26 }

上面默认采用了递增排序，如果要递减，就反向迭代并使用greater_equal。

为图简便，这里把元素直接放到输入的容器了。

整个测试程序：

 1 #include <iostream>
 2 #include <vector>
 3 #include <cassert>
 4 
 5 using namespace std;
 6 
 7 template<typename _InIt, typename _Func>
 8 void __insert_sort(_InIt first, _InIt last, _Func& Func) {
 9     typedef typename iterator_traits<_InIt>::value_type _ValueType;
10 
11     for (_InIt it = first+1; it != last+1; ++it) {
12         _ValueType key = *it;
13         _InIt ite = it - 1;
14         for (; (ite - first)>=0 && !Func(*ite, key); --ite)
15             *(ite + 1) = *ite;
16         *(ite + 1) = key;
17     }
18 }
19 
20 template<typename _InIt, typename _Func>
21 void insert_sort(_InIt first, _InIt last, _Func& Func) {
22     __insert_sort(first, last-1, Func);
23 }
24 
25 int bucket_index(int num, int p) {
26     assert(num >0 && p > 0);
27     int s = 1;
28     while (p-->0) s *= 10;
29     return ((num%s)*10)/s;
30 }
31 
32 template<typename _InIt>
33 void bucket_sort(_InIt first, _InIt last, short decimal_bits) {
34     typedef typename iterator_traits<_InIt>::value_type _ValueType;
35     typedef typename vector<_ValueType>::iterator _Iterator;
36 
37     int n = last - first;
38     if (n <= 0) return;
39 
40     vector< vector<_ValueType> > v(n, vector<_ValueType>());
41     _InIt it = first;
42     for(; it!=last; ++it) {
43         int i = bucket_index(*it, decimal_bits);
44         v[i].insert(v[i].begin(), *it);
45     }
46 
47     typename vector< vector<_ValueType> >::iterator ite = v.begin();
48     less_equal<_ValueType> cmp;
49     it = first;
50 
51     for(; ite!=v.end(); ++ite) {
52         if (ite->empty()) continue;
53         insert_sort(ite->begin(), ite->end(), cmp);
54         for(_Iterator _it=ite->begin(); _it!=ite->end(); ++_it)
55             *it++ = *_it;
56     }
57 }
58 
59 template<typename T>
60 void print(const vector<T>& v) {
61     for(vector<int>::const_iterator it=v.begin(); it != v.end(); it++)
62            cout << *it << " ";
63         cout << endl;
64 }
65 
66 int main() {
67     int lst[] = {78,17,39,26,72,94,21,12,23,68};
68     vector<int> v(lst, lst+10);
69 
70     bucket_sort(v.begin(), v.end(), 2);
71     print(v);
72 
73     return 0;
74 }

写完这些例子，在准备刷难度高一点的算法之前，小小的总结了一下。

这些例子的适用范围都很小，仅供学习使用，比如上面的插入排序，迭代器仅仅对vector有效，如果有自己的数据结构容器，最好是为它实现一个随机访问迭代器。