理解了基数排序，也就理解了桶排序。
桶排序就是基数排序的一种优化，从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有效，如果有自己的数据结构容器，最好是为它实现一个随机访问迭代器。