桶排序
當(dāng)待排序的隨機(jī)序列密集的分布于一個(gè)狹窄區(qū)間時(shí)，使用計(jì)數(shù)排序速度比較快，當(dāng)待排序的隨機(jī)序列比較均勻的分布于一個(gè)較寬區(qū)間時(shí)，可以考慮使用桶排序。桶排序的時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度也為O(n)。
既然一個(gè)待排序的隨機(jī)序列比較均勻的分布于一個(gè)區(qū)間，就很容易散列到各個(gè)桶中，假設(shè)有 n 個(gè)元素比較均勻的散列到 m 個(gè)桶中，則每個(gè)桶中的元素?cái)?shù)目約為 n/m，可以使用普通排序算法對(duì)每個(gè)桶中的元素排序，排序完畢后再把所有元素復(fù)制到最初序列的位置覆蓋原始序列。實(shí)際應(yīng)中n/m 通常很小，可以使用直接插入排序給每個(gè)桶中的元素排序，總的時(shí)間復(fù)雜度為O(n + m*(n/m)2 + n) = O(n2/m + 2n) = O(n)。如果每個(gè)桶的元素用鏈表存儲(chǔ)，鏈表可以用歸并排序，各桶排序完畢后把各個(gè)鏈表連接起來(lái)就可以了，省去一次復(fù)制元素的麻煩，這樣操作的時(shí)間復(fù)雜度為O(n + m(n/m)log(n/m)) = O(n + nlogk) = O(n)。
以隨機(jī)整數(shù)為例，桶排序過(guò)程如下表。
| 48 40 66 91 47 68 31 30 29 23 99 35 23 88 88 87 | 待排序的隨機(jī)序列 |
| 01 2 3 4 5 6 7 8 9 | 桶號(hào) |
| 29 23 23 31 30 35 48 40 47 66 68 88 88 87 91 99 | 散列(/10)到各個(gè)桶內(nèi) |
| 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 | 最終排序結(jié)果 |
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()); // 見(jiàn)本主頁(yè)的計(jì)數(shù)排序
26 unsigned long min = *min_element(v.begin(), v.end()); // 見(jiàn)本主頁(yè)的計(jì)數(shù)排序
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); // 插入排序見(jiàn)本主頁(yè)的快排
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 }