284 字
1 分钟
桶排序
桶排序(Bucket sort)
原理:将数值作为桶号,遍历整个数组,将相应的桶进行计数。
第一步:遍历原数组,找到最大值max,并且申请 max + 1 个桶,初始化都为0(下标从0到max),即vector
第二步:遍历原数组,找到每个数值对应的桶号,并对桶的计数++,即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;}