理解了基数排序，也就理解了桶排序。
桶排序就是基数排序的一种优化，从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有效，如果有自己的数据结构容器，最好是为它实现一个随机访问迭代器。
原文：http://www.cnblogs.com/danxi/p/6486653.html