数据结构学习之基数排序（含C++代码）

╰+哭是因爲堅強的太久メ 2023-06-04 12:58 7阅读 0赞

# 1.数据结构**学习之基数排序（含C++代码）** #

## 1.1.概念 ##

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

## 1.2.基本解法 ##

###     1.2.1第一步 ###

**     以下面的一列数为例，假设原来有一串数值如下所示：**

**     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**

###    1.2.2第二步 ###

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

**    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**

###    1.2.3第三步 ###

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

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

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

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

**代码如下：**

/*算法：基数排序*/
     
    #include <iostream>
     
    using namespace std;
    /*********************************************************
    Function:rxsort
    Description:基数排序
    Input:
        数组A[l,h]；
        数组中最大元素的位数d，例如最大数为999，则d为3；
        进制数k，如果是10进制数，k为10；
    Output:排序好的数组；
    Others：对数字1234来说，预定第0位为4，第1位为3，依次类推；
    *********************************************************/
    bool rxsort(int A[],int l,int h,int d,int k){
        if(NULL==A||l>h)
            return false;
        int size = h-l+1;
     
        int* counts = new int[k];//用于计数排序的辅助数据，详见计数排序
        int* temp = new int[size];//用于存储重新排序的数组
        int index;
        int pval=1;
        //依次处理不同的位
        for(int i=0;i<d;i++){
            //counts数组清零
            for(int j=0;j<k;j++)
                counts[j] = 0;
     
            for(int j=l;j<=h;j++){
                /*
                1.data[j]/pval：去掉数字data[j]的后i个数，例如：
                当data[j]=1234,i=2时，此时pval=100,data[j]/pval=12;
                2.(data[j]/pval)%k：取数字data[j]/pval的最后一位数
                3.(int)(data[j]/pval)%k:取数字data[j]的第i位数
                */
                index = (int)(A[j]/pval)%k;
                /*
                统计数组A中每个数字的第i位数中各个数字的频数,用于计数排序；
                */
                counts[index]++;
            }
            //计算累加频数，用户计数排序
            for(int j=1;j<k;j++)
                counts[j] = counts[j] + counts[j-1];
            //使用倒数第i+1位数对A进行排序
            for(int j=h;j>=l;j--){
                index = (int)(A[j]/pval)%k;
                temp[counts[index]-1] = A[j];
                counts[index]--;
            }
            //将按第i为数排序后的结果保存回数组A中
            for(int j=0;j<size;j++)
                A[j+l] = temp[j];
            //更新pval
            pval = pval*k;
        }
        delete[] counts;
        delete[] temp;
    }
     
    int main(){
        int A[] = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81};
        rxsort(A,0,9,2,10);
        for(int i=0;i<10;i++)
            cout<<A[i]<<" ";
    }

运行结果如下：  
![20191003145219135.png][]

[Link 1]: https://baike.baidu.com/item/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6/1894057
[20191003145219135.png]: /images/20230601/70e3e465133240318c57a145743fe14e.png