桶排序

本页面将简要介绍桶排序。

定义

桶排序（英文：Bucket sort）是排序算法的一种，适用于待排序数据值域较大但分布比较均匀的情况。

过程

桶排序按下列步骤进行：

1. 设置一个定量的数组当作空桶；
2. 遍历序列，并将元素一个个放到对应的桶中；
3. 对每个不是空的桶进行排序；
4. 从不是空的桶里把元素再放回原来的序列中。

性质

稳定性

如果使用稳定的内层排序，并且将元素插入桶中时不改变元素间的相对顺序，那么桶排序就是一种稳定的排序算法。

由于每块元素不多，一般使用插入排序。此时桶排序是一种稳定的排序算法。

时间复杂度

桶排序的平均时间复杂度为 $O(n+n^2/k+k)$（将值域平均分成 $n$ 块 + 排序 + 重新合并元素），当 $k\approx n$ 时为 $O(n)$。¹

桶排序的最坏时间复杂度为 $O(n^2)$。

实现

[list2tab]

• C++

  constexpr 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];
      }
    }
  }

• Python

  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

参考资料与注释

Footnotes

1. （英文）Bucket sort - Wikipedia ↩