桶排序
当待排序的随机序列密集的分布于一个狭窄区间时，使用计数排序速度比较快，当待排序的随机序列比较均匀的分布于一个较宽区间时，可以考虑使用桶排序。桶排序的时间复杂度为O(n)，空间复杂度也为O(n)。
既然一个待排序的随机序列比较均匀的分布于一个区间，就很容易散列到各个桶中，假设有 n 个元素比较均匀的散列到 m 个桶中，则每个桶中的元素数目约为 n/m，可以使用普通排序算法对每个桶中的元素排序，排序完毕后再把所有元素复制到最初序列的位置覆盖原始序列。实际应中n/m 通常很小，可以使用直接插入排序给每个桶中的元素排序，总的时间复杂度为O(n + m*(n/m)2 + n) = O(n2/m + 2n) = O(n)。如果每个桶的元素用链表存储，链表可以用归并排序，各桶排序完毕后把各个链表连接起来就可以了，省去一次复制元素的麻烦，这样操作的时间复杂度为O(n + m(n/m)log(n/m)) = O(n + nlogk) = O(n)。
以随机整数为例，桶排序过程如下表。
| 48 40 66 91 47 68 31 30 29 23 99 35 23 88 88 87 | 待排序的随机序列 |
| 01 2 3 4 5 6 7 8 9 | 桶号 |
| 29 23 23 31 30 35 48 40 47 66 68 88 88 87 91 99 | 散列(/10)到各个桶内 |
| 23 23 29 30 31 35 40 47 48 66 68 87 88 88 91 99 | 各桶分别排序 |
| 23 23 29 30 31 35 40 47 48 66 68 87 88 88 91 99 | 最终排序结果 |
1 inline unsigned long power2ceil(unsigned long x)
2 {
3 --x;
4 x |= x >> 1;
5 x |= x >> 2;
6 x |= x >> 4;
7 x |= x >> 8;
8 x |= x >> 16;
9 // x |= x >> 32;
10 return ++x;
11 }
12
13 inline unsigned long hash_bits(unsigned long x)
14 {
15 unsigned long sum = 0;
16 for(; x > 1; x >>= 1)
17 ++sum;
18 return sum;
19 }
20
21 // non-portable implementation only for unsigned long type
22 template <typename Compare>
23 void bucket_sort(std::vector<unsigned long>& v, Compare cmp)
24 {
25 unsigned long max = *max_element(v.begin(), v.end()); // 见本主页的计数排序
26 unsigned long min = *min_element(v.begin(), v.end()); // 见本主页的计数排序
27 unsigned long max_bits = hash_bits(power2ceil(max - min));
28 unsigned long base = hash_bits(power2ceil(v.size()) / 100);
29 unsigned long bins = 1 << base;
30 unsigned long offset = (max_bits <= base ? base >> 7 : max_bits - base);
31 unsigned long pits = 128;
32 typedef std::vector<unsigned long> VECTOR;
33 std::vector<VECTOR> vec(bins + 1);
34 for(VECTOR::size_type i = 0; i < vec.size(); ++i)
35 vec[i].reserve(pits);
36 for(VECTOR::size_type i = 0; i < v.size(); ++i)
37 vec[(v[i] - min) >> offset].push_back(v[i]);
38 for(VECTOR::size_type i = 0; i < vec.size(); ++i)
39 insertion_sort(vec[i].begin(), vec[i].end(), cmp); // 插入排序见本主页的快排
40 unsigned long k = 0;
41 for(std::vector<VECTOR>::size_type i = 0; i < vec.size(); ++i)
42 for(VECTOR::size_type j = 0; j < vec[i].size(); ++j)
43 v[k++] = vec[i][j];
44 }