桶排序
本页面将简要介绍桶排序。
定义
桶排序（英文：Bucket sort）是排序算法的一种，适用于待排序数据值域较大但分布比较均匀的情况。
过程
桶排序按下列步骤进行：
- 设置一个定量的数组当作空桶；
- 遍历序列，并将元素一个个放到对应的桶中；
- 对每个不是空的桶进行排序；
- 从不是空的桶里把元素再放回原来的序列中。
性质
稳定性
如果使用稳定的内层排序，并且将元素插入桶中时不改变元素间的相对顺序，那么桶排序就是一种稳定的排序算法。
由于每块元素不多，一般使用插入排序。此时桶排序是一种稳定的排序算法。
时间复杂度
桶排序的平均时间复杂度为 \(O(n + n^2/k + k)\)（将值域平均分成 \(n\) 块 + 排序 + 重新合并元素），当 \(k\approx n\) 时为 \(O(n)\)。
桶排序的最坏时间复杂度为 \(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
34 | #include<bits/stdc++.h>
using namespace std;
vector<int> bucketSort(vector<int> &a){ //也可以是无返回值函数void *a指针传递
int maxValue=*max_element(a.begin(),a.end()); //返回的是迭代器
int minValue=*min_element(a.begin(),a.end());
int n=a.size();
//差异率公式=（max-min)/n
int bucketCnt=(maxValue-minValue)/n+1;
//建桶
vector<vector<int>> bucketArray(bucketCnt);
//元素放入桶内
for (auto &&i : a) bucketArray[(i-minValue)/n].push_back(i); //计算该放入的桶的编号
//桶内排序
for (auto &&b : bucketArray) sort(b.begin(),b.end());
a.clear();//原a清空
//重新倒出
for (auto &&b : bucketArray) a.insert(a.end(),b.begin(),b.end());
return a;
}
int main(){
vector<int> a={7,12,56,23,19,33,35,42,42,2,8,22,39,26,17};
for (auto &&i : a) printf("%d ",i);
cout<<endl;
vector<int> b=bucketSort(a); //vector b是函数的返回
for (auto &&i : a) printf("%d ",i);
cout<<endl;
for (auto &&i : b) printf("%d ",i);
cout<<endl;
return 0;
}
|
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 | def bucketSort(a):
max_val = max(a)
min_val = min(a)
n = len(a)
# 计算桶的数量
bucket_cnt = int((max_val - min_val) / n) + 1
bucket_array = [[] for _ in range(bucket_cnt)]
# 分配元素到桶
for num in a:
index = int((num - min_val) / n)
bucket_array[index].append(num)
# 对每个桶排序
for bucket in bucket_array:
bucket.sort()
# 合并桶
a .clear()
for bucket in bucket_array:
a.extend(bucket)
return a
a = [0, 213, 235, 11, 2, 2, 3, 5, 6, 87, 98, 9, 0, 1, 23, 43, 54, 1, 1, 516, 5]
print("原始数组:", a)
b = bucketSort(a)
print("排序后数组:", b)
print("原数组是否被修改:", a)
|
参考资料与注释