排序算法八--基数排序

Love The Way You Lie 2022-05-10 14:58 272阅读 0赞

基数排序(radix sort)是一种特殊的桶排序（bucket sort），相对于常见的比较排序，基数排序是一种分配式排序，即通过将所有数字分配到应在的位置最后再覆盖到原数组完成排序的过程。它是一种稳定的排序算法，但有一定的局限性：   
1、关键字可分解；   
2、记录的关键字位数较少，如果密集更好；   
3、如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序。   
初始化：构造一个10\*n的二维数组，一个长度为n的数组用于存储每次位排序时每个桶子里有多少个元素。   
循环操作：从低位开始（我们采用LSD的方式），将所有元素对应该位的数字存到相应的桶子里去（对应二维数组的那一列）。然后将所有桶子里的元素按照桶子标号从小到大取出，对于同一个桶子里的元素，先放进去的先取出，后放进去的后取出（保证排序稳定性）。这样原数组就按该位排序完毕了，继续下一位操作，直到最高位排序完成。   
待排序的数组：70, 34, 65, 24, 48, 32, 88, 16, 38, 81   
按个位排序：

![70][]  
代码实现：

public static void RadixSort(int A[],int temp[],int n,int k,int r,int cnt[]){
    
       //A:原数组
       //temp:临时数组
       //n:序列的数字个数
       //k:最大的位数2
       //r:基数10
       //cnt:存储bin[i]的个数
    
       for(int i=0 , rtok=1; i<k ; i++ ,rtok = rtok*r){
    
           //初始化
           for(int j=0;j<r;j++){
               cnt[j] = 0;
           }
           //计算每个箱子的数字个数
           for(int j=0;j<n;j++){
               cnt[(A[j]/rtok)%r]++;
           }
           //cnt[j]的个数修改为前j个箱子一共有几个数字
           for(int j=1;j<r;j++){
               cnt[j] = cnt[j-1] + cnt[j];
           }
           for(int j = n-1;j>=0;j--){      //重点理解
               cnt[(A[j]/rtok)%r]--;
               temp[cnt[(A[j]/rtok)%r]] = A[j];
           }
           for(int j=0;j<n;j++){
               A[j] = temp[j];
           }
       }
    }

参考地址：https://blog.csdn.net/lyhkmm/article/details/78920769

[70]: /images/20220505/adfe3f1b1f3c46e1a058343fd02a8a72.png