284 字
1 分钟
桶排序

桶排序(Bucket sort)#

原理:将数值作为桶号,遍历整个数组,将相应的桶进行计数。

第一步:遍历原数组,找到最大值max,并且申请 max + 1 个桶,初始化都为0(下标从0到max),即vector bucket(max + 1, 0);

第二步:遍历原数组,找到每个数值对应的桶号,并对桶的计数++,即bucket[a[i]]++;

第三步:遍历桶数组,看到对应的桶内计数为几就取出几个下标值,放到原数组

C++代码如下:#

#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
void Bucket_sort(vector<int> &v) {
int max = v[0];
for (int i = 1; i < v.size(); ++i) {
if (v[i] > max) {
max = v[i];
}
}
//根据最大值创建一个桶
vector<int> bucket(max + 1, 0);
//在桶中统计待排序元素个数
for (int i = 0; i < v.size(); ++i) {
bucket[v[i]]++;
}
//复原待排序数组
int Index = 0;
for (int i = 0; i < max + 1; ++i) {
while (bucket[i]--) {
v[Index++] = i;
}
}
}
int main() {
vector<int> vec = { 8, 2, 3, 4, 6, 5, 3, 8, 1 };
int n = 9;
Bucket_sort(vec);
for (int i = 0; i < n; ++i) {
cout << vec[i] << " ";
}
return 0;
}
桶排序
https://fuwari.cbba.top/posts/桶排序/
作者
Chen_Feng
发布于
2023-02-19
许可协议
CC BY-NC-SA 4.0