前言
一种将无序数组进行排序的方法。
桶排序，wiki参考：
https://zh.wikipedia.org/wiki/%E6%A1%B6%E6%8E%92%E5%BA%8F
需要引入额外的临时数组。
这个排序算法比较特殊。
个人理解：
- 当数据在一定范围内（小）波动，每一个桶对应一种数据，利用桶排序是极其简单快速的。
- 当数据波动较大时，每一个桶均对应一个数据段，有点类似归并排序算法。
举个例子：
- 若原数组是[4, 2, 2, 0]
- 将桶数组（临时引入的数组）初始为 [0, 0, 0, 0, 0],桶的索引对应了原数组的数据区间
- 当遍历原数组第一个元素4时，则桶数组[4] 加1，桶数组变为 [0, 0, 0, 0, 1]。用映射替代了比较，实现排序。
- 当遍历完原数组，则桶数组变成[1, 0, 2, 0, 1]。代表了 1个0， 0个1， 2个2， 0个3， 1个4。并且只要遍历桶数组即可获得合适的排序结果。无需任何的比较。
在这里，只会讨论数据范围小，使用桶排序的情况。当范围大时，我十分可能不会考虑桶排序。
这里举例 0 - 99 范围内随机数进行排序的一种桶排序算法。再次强调一下，这种情况下，桶排序是十分简单而快速的算法。
环境
编辑器：vs2019
文件：.c类型
正文
参考代码：
#include <stdio.h>
// 桶排序
// 用映射关系替代两数之间的比较。
// 这里讨论小范围内（0-99随机数）的桶排序算法实现。
// 扩充为大范围的桶排序算法，大多数做法为链表。并且此时的桶排序，总体看来有些归并算法的意味。
// 主要思路
// 1. 实现100个桶，分别对应 0 - 99。
// 2. 每遍历到一个数，对应的桶值自增。
// 3. 最后利用桶本身的顺序，直接输出即可。
//注意，这个函数需要输入的数组值在 0 - 99范围内波动
void bucket_sort_normal(int source_array[], int source_array_length)
{
int i, j, k;
// 1. 创建100个桶，并初始化为 0。
int tmp_bucket[100] = {0};
// 2. 将桶索引视为数组的“元素”，桶索引对应的值就是数组“该元素的个数”。
for (i = 0; i < source_array_length; i++)
{
// 比如， 若原数组是[4, 2, 1, 0]
// 桶数组初始为 [0, 0, 0, 0, 0],桶的索引对应了原数组的数据区间
// 当遍历原数组第一个元素4时，则桶数组[4] 加1，桶数组变为 [0, 0, 0, 0, 1]。用映射替代了比较，实现排序。
tmp_bucket[source_array[i]]++;
}
// 遍历桶数组(桶数组长度100)，改变原数组
j = 0;
for (i = 0; i < 100; i++)
{
for (k = 0; k < tmp_bucket[i]; k++)
{
source_array[j] = i;
j++;
}
}
}
int main()
{
// 生成随机测试列表 0-99
int test_list[20];
int test_list_length = sizeof(test_list) / sizeof(int);
printf("测试列表： \n");
for (int i = 0; i < test_list_length; i++)
{
test_list[i] = rand() % 100;
printf("%d ", test_list[i]);
}
printf("\n");
// 普通桶排序
bucket_sort_normal(test_list, test_list_length);
printf("普通桶排序结果： \n");
for (int i = 0; i < test_list_length; i++)
{
printf("%d ", test_list[i]);
}
printf("\n");
return 0;
}
执行结果参考：
image.png
扩展
桶排序的扩展：一个桶对应多个数据。在下一篇的 基数排序 中会有体现。
