跳转至

桶排序

本頁面將簡要介紹桶排序。

定義

桶排序（英文：Bucket sort）是排序算法的一種，適用於待排序數據值域較大但分佈比較均勻的情況。

過程

桶排序按下列步驟進行：

  1. 設置一個定量的數組當作空桶；
  2. 遍歷序列，並將元素一個個放到對應的桶中；
  3. 對每個不是空的桶進行排序；
  4. 從不是空的桶裏把元素再放回原來的序列中。

性質

穩定性

如果使用穩定的內層排序，並且將元素插入桶中時不改變元素間的相對順序，那麼桶排序就是一種穩定的排序算法。

由於每塊元素不多，一般使用插入排序。此時桶排序是一種穩定的排序算法。

時間複雜度

桶排序的平均時間複雜度為 \(O(n + n^2/k + k)\)（將值域平均分成 \(n\) 塊 + 排序 + 重新合併元素），當 \(k\approx n\) 時為 \(O(n)\)。1

桶排序的最壞時間複雜度為 \(O(n^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
const int N = 100010;

int n, w, a[N];
vector<int> bucket[N];

void insertion_sort(vector<int>& A) {
  for (int i = 1; i < A.size(); ++i) {
    int key = A[i];
    int j = i - 1;
    while (j >= 0 && A[j] > key) {
      A[j + 1] = A[j];
      --j;
    }
    A[j + 1] = key;
  }
}

void bucket_sort() {
  int bucket_size = w / n + 1;
  for (int i = 0; i < n; ++i) {
    bucket[i].clear();
  }
  for (int i = 1; i <= n; ++i) {
    bucket[a[i] / bucket_size].push_back(a[i]);
  }
  int p = 0;
  for (int i = 0; i < n; ++i) {
    insertion_sort(bucket[i]);
    for (int j = 0; j < bucket[i].size(); ++j) {
      a[++p] = bucket[i][j];
    }
  }
}

 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
N = 100010
w = n = 0
a = [0] * N
bucket = [[] for i in range(N)]

def insertion_sort(A):
    for i in range(1, len(A)):
        key = A[i]
        j = i - 1
        while j >= 0 and A[j] > key:
            A[j + 1] = A[j]
            j -= 1
        A[j + 1] = key

def bucket_sort():
    bucket_size = int(w / n + 1)
    for i in range(0, n):
        bucket[i].clear()
    for i in range(1, n + 1):
        bucket[int(a[i] / bucket_size)].append(a[i])
    p = 0
    for i in range(0, n):
        insertion_sort(bucket[i])
        for j in range(0, len(bucket[i])):
            a[p] = bucket[i][j]
            p += 1

參考資料與註釋

  1. （英文）Bucket sort - Wikipedia ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用