【注】参考自教材「算法导论」。

1. 简介

  桶排序是将待排序序列分到有限数量的桶中,然后对每一个桶分别进行排序。桶排序的前提假设为被排序序列的关键字数值符合均匀分布,此时桶排序的平均时间复杂度为 O(n+n2k+k)O(n + {n^2 \over k} + k),最坏时间复杂度为 O(n2)O(n^2),其中 kk 为桶的数量。当桶数量 knk \approx n 时,此时桶排序的复杂度为线性复杂度 O(n)O(n)

  桶排序是非原址的,其稳定性取决于内层排序的稳定性。一般采用稳定的插入排序作为内层排序算法,此时桶排序是稳定的。

2. 思想

桶排序的主要思想是对待排序序列的关键字数值进行分块,每一块对应一个桶,然后对每个桶使用插入排序(或其他排序算法)进行排序,最后将所有桶中的元素串联起来即得到有序序列。

3. 实现

3.1 伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
BucketSort(A, mx, n) {
// mx 为最大数值,n 为桶数量
// 定义 n 个桶
define bucket[n]
// 计算分块的块大小
bucketsize = mx/n + 1
// 根据元素的排序关键字数值分块
for i = 1 to A.length
bucket[A[i]/bucketsize].PushBack(A[i])
for i = 0 to n-1
InsertSort(bucket[i])
cnt = 0
for i = 0 to n-1
for j = 1 to bucket[i].length
A[++cnt] = bucket[i][j]
}

3.2 模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;

#ifndef _BUCKET_
#define _BUCKET_
#define ll int
#define MAXN 100005
#define MAXBUK 1000
#define INF 10000000

// 桶排序
template < typename T >
struct Bucket {
vector < pair<T, ll> > bucket[MAXN];
Bucket() {}
// 插入排序
void insertSort(vector < pair<T, ll> > & bkt) {
for(ll i = 1; i < bkt.size(); ++i) {
pair <T, ll> key = bkt[i];
ll j = i - 1;
while(~j && bkt[j].second > key.second) {
bkt[j+1] = bkt[j];
j--;
}
bkt[j+1] = key;
}
}
// 桶排序
void bucketSort(T *bA, T *eA, ll *bK, ll *eK, ll mx = INF, ll bn = MAXBUK) {
ll len_A = eA - bA;
ll len_K = eK - bK;
T *A = bA;
ll *K = bK;
ll bucketsize = mx/bn + 1;
// 判断关键字数组大小与元素数组大小是否吻合
assert(len_A == len_K);
// 初始化桶
for(ll i = 0; i < bn; ++i) {
bucket[i].clear();
}
// 将元素放入桶中
for(ll i = 0; i < len_K; ++i) {
bucket[K[i]/bucketsize].push_back(pair<T, ll>{A[i], K[i]});
}
// 对每一个桶进行插入排序
ll cnt = 0;
for(ll i = 0; i < bn; ++i) {
insertSort(bucket[i]);
for(ll j = 0; j < bucket[i].size(); ++j) {
A[cnt++] = bucket[i][j].first;
}
}

}
};
#endif