桶排序

當待排序的隨機序列密集的分布于一個狹窄區間時，使用計數排序速度比較快，當待排序的隨機序列比較均勻的分布于一個較寬區間時，可以考慮使用桶排序。桶排序的時間復雜度為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 }