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

1. 简介

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