桶排序

当待排序的随机序列密集的分布于一个狭窄区间时,使用计数排序速度比较快,当待排序的随机序列比较均匀的分布于一个较宽区间时,可以考虑使用桶排序。桶排序的时间复杂度为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 }