排序算法第四谈：基数排序

骑猪看日落 2023-01-02 12:25 126阅读 0赞

## 一、思想 ##

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

## 二、图解过程 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODk1Mzk3_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODk1Mzk3_size_16_color_FFFFFF_t_70 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODk1Mzk3_size_16_color_FFFFFF_t_70 2]

## 三、核心代码 ##

/** * 基数排序 * 构造一个桶，每个数按位数分别放入桶中，放完后，从桶中取出数据放入数组 */
        public static void barrelSort(int[] arr) { 
            int[][] barrel = new int[10][arr.length];//考虑最坏的情况
            //为了保证回收的时候知道每个桶中放了多少个数据
            int[] barreCount = new int[10];
            //按位数确定循环次数，所以需要提前知道最大数长度
            int leght = (getMax(arr) + "").length();
            for (int i = 0, m = 1; i < leght; i++, m *= 10) { 
                //每次循环，按当前位的数子放入桶中
                for (int j = 0; j < arr.length; j++) { 
                    int temp = (arr[j] / m) % 10;//当前位数的数字
                    barrel[temp][barreCount[temp]++] = arr[j];
                }
                //从桶中一次取出数据放回原数组
                int indexBarre = 0;//当前数组索引
                for (int j = 0; j < 10; j++) { 
                    if (barreCount[j] != 0) { 
                        for (int n = 0; n < barreCount[j]; n++) { 
                            arr[indexBarre++] = barrel[j][n];
                        }
                    }
                    barreCount[j] = 0;
                }
            }
        }
        public static int getMax(int[] arr) { 
            int max = arr[0];
            for (int i = 0; i < arr.length; i++) if (max < arr[i]) max = arr[i];
            return max;
        }

## 四、速度测试 ##

![image.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODk1Mzk3_size_16_color_FFFFFF_t_70]: /images/20221119/2838dd482e9946b3b1f7e45fb2242922.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODk1Mzk3_size_16_color_FFFFFF_t_70 1]: /images/20221119/cf9338d4ad0d4b548d707a462639c33e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODk1Mzk3_size_16_color_FFFFFF_t_70 2]: /images/20221119/b72cfcf8fb374cd0b87376004565d91f.png
[image.png]: /images/20221119/4b1e772c9bc44edea36f447681fdb3bd.png