资深光能
桶计数：
桶数组：一个数组两个信息（下标是计数对象，值是出现次数）
举个例子：比如桶数组b[4]
这个数组的元素多少是看题目中最大的数是多少，比如最大的是10，那数组至少有11个元素。
比如：1 2 2这三个数
元素： b[1] b[2] b[3]
次数： 1 2 0
对准计数： 1 2 3
注意一下：
桶的初值是0
b[x]=y的含义是x出现了y次
以上纯属手打
李雨彤在2021-11-26 20:45:37追加了内容
冒泡、选择、插入、堆排、归并、荷兰国旗、快排等都是基于比较的排序。桶排是根据数据状况做的计数排序，在range少，比如年龄（1-200），数据多的时候非常好用。如果你理解词频统计，那么就能理解什么是桶排。时间复杂度为O(N)。
步骤：
1.取最大值，其余补足位数 比如最大值为100 23->023
2.建10个队列，就是10个桶 分别对应数字[0-9]
3. for() 个位 十位 百位..进队列排 就是按个、十、百、千...有序，最后数字就有序了。
3.1.d=1 个位 统计数字 从左到右
比如数组是[ 022，021， 032， 031， 001， 100]
1 3 2 0 0 0 0 0 0 0
count[0 1 2 3 4 5 6 7 8 9] 含义为个位上每个数有几个
3.2 统计每位上 <<=0 《=1有几个 从左到右
1 4 6 6 6 6 6 6 6 6
count`[0 1 2 3 4 5 6 7 8 9]
3.3 进桶 从右到左
0~0 上一个 搞定0位置 100
0~3 上4个 搞定3位置 001
0~2 上3个 搞定2位置
3.4出桶 复制回原来的数组 从左到右
上代码
//取相应的位数
int getDigit(int x, int d) {
return ((x / ((int)pow(10, d - 1))) % 10);
}
void radixProcess(int arr[], int m_num, int begin, int end, int digit)
{
int radix = 10;//固定的 长度为[0..9]
int i = 0, j = 0;
// int* bucket = new int[m_num+1];//有多少数就准备个多大的辅助空间
int bucket[11] = {0};
for (int d = 1; d <= digit; d++) //有多少位就进出几次 d=1表示个位 =2表示十位 =3表示百位
{
//int* count = new int[radix]; //统计数组 ，长度为[0..9] 每次都是10个
int count[10] = {0};
//1.取得每个数组值每位的值 遍历次数 数组个数，从左往右， 取得每个数组值每位的值
for (i = begin; i <= end; i++)
{
j = getDigit(arr[i], d);
count[j]++;
}
//2.统计《=0，《=1 值，0-9 遍历10次 0-9 从左往右 位数字统计 <=0 《=1总共有有几个
for (i = 1; i < radix; i++)
{
count[i] = count[i] + count[i - 1];
}
//3.遍历次数 ，数组个数， 从右往左，把值放入bucket[]中
//数组值进辅助空间
for (i = end; i >= begin; i--)
{
j = getDigit(arr[i], d);
bucket[count[j] - 1] = arr[i];
count[j]--;
}
//4.拷贝回原数组
for (i = begin, j = 0; i <= end; i++, j++)
{
arr[i] = bucket[j];
}
}
}
// 取最大值 得到位数
int maxbits(int arr[],int m_num) {
int max =0 ;
for (int i = 0; i < m_num; i++) {
max=(max>arr[i])? max: arr[i];
}
int res = 0;
while (max != 0) {
res++;
max /= 10;
}
return res;
}
void radixSort_main(int arr[], int m_num)
{
cout << "radixSort******************" << endl;
if (arr == NULL || m_num < 2) { return; }
radixProcess(arr, m_num,0, m_num - 1, maxbits(arr, m_num));
for (int i = 0; i < m_num; i++)
{
cout << arr[i] << endl;
}
}李雨彤在2021-11-26 20:47:44追加了内容
桶排序
基本思想
先扫描得到待排序数组中的最大值maxVal与最小值minVal，假设桶的个数为k，则代表则将[minVal, maxVal]均分为k个范围，每个范围中的元素各自放入对应的桶中。如此桶之间必然是有序的，桶内使用排序算法进行排序，最后按序收集所有桶的元素，即完成桶排序；
复杂度
时间复杂度
总的时间复杂度为 O(n)+O(k)O(n/klog(n/k)) = O(n+nlog(n/k))
当 k 接近于 n 时，桶排序的时间复杂度就可以金斯认为是 O(n) 的。即桶越多，时间效率就越高，而桶越多，空间就越大。
空间复杂度：O(n+k)
以上摘自CSDN
————————————————
版权声明：本文为CSDN博主「xin_hen」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/xin_hen/article/details/108032465
