docs/basic/bucket-sort.md
本页面将简要介绍桶排序．
桶排序（英文：Bucket sort）是排序算法的一种，适用于待排序数据值域较大但分布比较均匀的情况．
桶排序按下列步骤进行：
如果使用稳定的内层排序，并且将元素插入桶中时不改变元素间的相对顺序，那么桶排序就是一种稳定的排序算法．
由于每块元素不多，一般使用插入排序．此时桶排序是一种稳定的排序算法．
桶排序的平均时间复杂度为 $O(n + n^2/k + k)$（将值域平均分成 $n$ 块 + 排序 + 重新合并元素），当 $k\approx n$ 时为 $O(n)$．1
桶排序的最坏时间复杂度为 $O(n^2)$．
=== "C++" ```cpp 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" ```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
```