前言

一种将无序数组进行排序的方法。

基数排序，百度参考：
https://baike.baidu.com/item/基数排序/7875498?fr=aladdin

基数排序利用了桶排序的思想。

基数排序也如桶排序一样特殊。
个人理解：

1. 数据在一定范围内波动，比如 0-99999
2. 数据的量不能太大，这点在桶排序中并没有限制。
3. 相比于桶排序，基数排序更适合用于 值范围大，但是数据量小 的情况。而桶排序更适合用于 值范围小，数据量没有要求 的情况。

这里举例了一种在 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