排序方法（8）：基数排序

不念不忘少年蓝@ 2022-05-28 13:37 130阅读 0赞

# 基数排序 #

参考：  
[https://baike.baidu.com/item/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F][https_baike.baidu.com_item_E5_9F_BA_E6_95_B0_E6_8E_92_E5_BA_8F]

[http://cuijiahua.com/blog/2018/01/algorithm\_8.html][http_cuijiahua.com_blog_2018_01_algorithm_8.html]

## 一、原理 ##

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

## 二、步骤 ##

*  1、将所有数据从低位开始，按照0~9进行归类
 *  2、将归完的数据整理好，这就进行了一次排序
 *  3、重复执行前两步直到最高位也排完序了，此时整理完数据就是排完的序列

## 三、例子（借用百度百科的例子） ##

*  第一步

以LSD为例，假设原来有一串数值如下所示：

73, 22, 93, 43, 55, 14, 28, 65, 39, 81

首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：

0
    1 81
    2 22
    3 73 93 43
    4 14
    5 55 65
    6
    7
    8 28
    9 39

*  第二步

接下来将这些桶子中的数值重新串接起来，成为以下的数列：

81, 22, 73, 93, 43, 14, 55, 65, 28, 39

接着再进行一次分配，这次是根据十位数来分配：

0
    1 14
    2 22 28
    3 39
    4 43
    5 55
    6 65
    7 73
    8 81
    9 93

*  第三步

接下来将这些桶子中的数值重新串接起来，成为以下的数列：

14, 22, 28, 39, 43, 55, 65, 73, 81, 93

这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。

LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。

## 四、算法实现 ##

### C语言 ###

#include "stdio.h"
    #include "math.h"
    
    void bucketSort3(int *p, int n);
    int getLoopTimes(int num);
    int findMaxNum(int *p, int n);
    void sort2(int *p, int n, int loop);
    
    
    //基数排序
    void bucketSort3(int *p, int n)
    {
        //获取数组中的最大数
        int maxNum = findMaxNum(p, n);
        //获取最大数的位数，次数也是再分配的次数。
        int loopTimes = getLoopTimes(maxNum);
        int i;
        //对每一位进行桶分配
        for (i = 1; i <= loopTimes; i++)
        {
            sort2(p, n, i);
            printf("第%d次循环：\t", i);
            for (int j = 0; j < n; j++)
            {
                printf("%d\t", p[j]);
            }
            printf("\n");
        }
    }
    //获取数字的位数
    int getLoopTimes(int num)
    {
        int count = 1;
        int temp = num / 10;
        while (temp != 0)
        {
            count++;
            temp = temp / 10;
        }
        return count;
    }
    //查询数组中的最大数
    int findMaxNum(int *p, int n)
    {
        int i;
        int max = 0;
        for (i = 0; i < n; i++)
        {
            if (*(p + i) > max)
            {
                max = *(p + i);
            }
        }
        return max;
    }
    //将数字分配到各自的桶中，然后按照桶的顺序输出排序结果
    void sort2(int *p, int n, int loop)
    {
        //建立一组桶此处的20是预设的根据实际数情况修改
        int buckets[10][20] = {};
        //求桶的index的除数
        //如798个位桶index=(798/1)%10=8
        //十位桶index=(798/10)%10=9
        //百位桶index=(798/100)%10=7
        //tempNum为上式中的1、10、100
        int tempNum = (int)pow((float)10, loop - 1);
        int i, j;
        for (i = 0; i < n; i++)
        {
            int row_index = (*(p + i) / tempNum) % 10;
            for (j = 0; j < 20; j++)
            {
                if (buckets[row_index][j] == NULL)
                {
                    buckets[row_index][j] = *(p + i);
                    break;
                }
            }
        }
        //将桶中的数，倒回到原有数组中
        int k = 0;
        for (i = 0; i < 10; i++)
        {
            for (j = 0; j < 20; j++)
            {
                if (buckets[i][j] != NULL)
                {
                    *(p + k) = buckets[i][j];
                    buckets[i][j] = NULL;
                    k++;
                }
            }
        }
    }
    
    int main()
    {
        int a[] =  { 73, 22, 93, 43, 55, 14, 28, 65, 39, 81 };//{ 2, 343, 342, 1, 123, 43, 4343, 433, 687, 654, 3 };//
        int *a_p = a;
        int i;
        //计算数组长度
        int size = sizeof(a) / sizeof(int);
        printf("原始数据：\n");
        for (i = 0; i < size; i++)
        {
            printf("%d\t", a[i]);
        }
        printf("\n\n");
        //基数排序
        bucketSort3(a_p, size);
        //打印排序后结果
    
        printf("\n返回结果：\n");
        for (i = 0; i < size; i++)
        {
            printf("%d\t", a[i]);
        }
        printf("\n");
    }

### 运行结果 ###

![这里写图片描述][SouthEast]

[https_baike.baidu.com_item_E5_9F_BA_E6_95_B0_E6_8E_92_E5_BA_8F]: https://baike.baidu.com/item/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F
[http_cuijiahua.com_blog_2018_01_algorithm_8.html]: http://cuijiahua.com/blog/2018/01/algorithm_8.html
[SouthEast]: /images/20220528/b60b8e694dd243f1a5d1dbd51cf178cc.png