前言
一种将无序数组进行排序的方法。
基数排序，百度参考：
https://baike.baidu.com/item/基数排序/7875498?fr=aladdin
基数排序利用了桶排序的思想。
基数排序也如桶排序一样特殊。
个人理解：
- 数据在一定范围内波动，比如 0-99999
- 数据的量不能太大，这点在桶排序中并没有限制。
- 相比于桶排序，基数排序更适合用于 值范围大，但是数据量小 的情况。而桶排序更适合用于 值范围小，数据量没有要求 的情况。
这里举例了一种在 0-99 范围内，数组长度在20以内的基数排序。根据不同的情况，需要调整参数（桶排序也是如此）。
环境
编辑器：vs2019
文件：.c类型
正文
代码参考：
#include <stdio.h>
// 基数排序
// 基数排序利用了桶排序的思想。
// 1. 原数组 [111, 57, 0, 21, 65, 212, 311]
// 2. 建立10个二维桶数组：类似于 [][0,0,0,0,0,0,0]，第一维代表了0-9，第二维用于存放数据。
// 3. 第一次通过个位的数字，放入合适的桶中。
// 4. 第二次通过十位的数字，放入合适的桶中。
// 5. 第三次通过百位的数字，放入合适的桶中。
// 6. 直接遍历出来即可得到有序的数组。
// 另，这种从低位开始的方法叫做LSD，从高位开始的方法叫做MSD。
// 求个位，十位，百位的方法：
// int i = 123 / 1 % 10;
// int i = 123 / 10 % 10;
// int i = 123 / 100 % 10;
// 限制数组的数据在0-99。
// 限制数组中数据的个数为20个以内。
// 基数排序，从小到大，LSD。
void radix_sort_normal(int source_array[], int source_array_length)
{
int i, j, k;
// 创建桶, 数组长度应小于第二维的数组长度。这里是20
int tmp_bucket[10][20];
// 初始化桶，所有值填充-1， 当不为-1时，则代表存入了数据。
for (i = 0; i < 10; i++)
{
for (j = 0; j < 20; j++)
{
tmp_bucket[i][j] = -1;
}
}
// 位数
int digits = 1;
// 位数对应的索引
int digits_index;
while (digits <= 10)
{
// 将数据放入桶中。
for (i = 0; i < source_array_length; i++)
{
digits_index = source_array[i] / digits % 10;
for (j = 0; j < 20; j++)
{
if (tmp_bucket[digits_index][j] == -1)
{
tmp_bucket[digits_index][j] = source_array[i];
break;
}
}
}
// 替换原数组
k = 0;
for (i = 0; i < 10; i++)
{
for (j = 0; j < 20; j++)
{
if (tmp_bucket[i][j] != -1)
{
source_array[k] = tmp_bucket[i][j];
// 还原桶
tmp_bucket[i][j] = -1;
k++;
}
}
}
// 进行下一位操作
digits *= 10;
}
}
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");
// 普通基数排序
radix_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
