基数排序

客官°小女子只卖身不卖艺 2022-01-29 02:01 285阅读 0赞

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

图示  
![在这里插入图片描述][20190520174045223.png_x-oss-type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nX2Jv_size_16_color_FFFFFF_t_70]  
Java代码实现

//基数排序
    public int[] radixSort(int[] arr) { 
           int length = arr.length;
           int divisor = 1;// 定义每一轮的除数，1,10,100...
           int[][] bucket = new int[10][length];// 定义了10个桶，以防每一位都一样全部放入一个桶中
           int[] count = new int[10];// 统计每个桶中实际存放的元素个数
           int digit;// 获取元素中对应位上的数字，即装入那个桶
           for (int i = 1; i <= 3; i++) { // 经过4次装通操作，排序完成
               for (int temp : arr) { // 计算入桶
                   digit = (temp / divisor) % 10;
                   bucket[digit][count[digit]++] = temp;
               }
               int k = 0;// 被排序数组的下标
               for (int b = 0; b < 10; b++) { // 从0到9号桶按照顺序取出
                   if (count[b] == 0)// 如果这个桶中没有元素放入，那么跳过
                       continue;
                   for (int w = 0; w < count[b]; w++) { 
                       arr[k++] = bucket[b][w];
                   }
                   count[b] = 0;// 桶中的元素已经全部取出，计数器归零
               }
               divisor *= 10;
           }
           return arr;
       }

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

*  基数排序：根据键值的每位数字来分配桶
 *  计数排序：每个桶只存储单一键值
 *  桶排序：每个桶存储一定范围的数值

拓展：  
[http://cmsblogs.com/?p=4703][http_cmsblogs.com_p_4703]

[20190520174045223.png_x-oss-type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nX2Jv_size_16_color_FFFFFF_t_70]: /images/20220129/9a886c488a574db695366702e529ef68.png
[http_cmsblogs.com_p_4703]: http://cmsblogs.com/?p=4703