本文共 4311 字，大约阅读时间需要 14 分钟。

排序算法——基数排序（Radix Sort）

1. 基本介绍：基数排序属于分配式排序（distribution sort），又称桶子法（bucket sort），是桶排序的扩展。是一种稳定性的排序。基本原理是将整数按位数切割成不同的数字，然后按每个位数分别进行比较。
2. 思想分析：将所有待比较的数值统一为同样的数位长度，数位短的在前面补零。然后从最低位开始，依次进行一次排序。当从最低位一直排到最高位以后，在输出的数列就是有序序列。
3. 图文分析说明：
   
   一共十个桶，分别代表从0-9的十个数，然后第一次按照各位进行排序，按照队列先进先出的原则进行添加。直到比到最后一位在输出，即为排序过后的数组。
   
4. 代码实现：
   分解代码：

第一次循环：int[][] bucket = new int[10][arr.length];        int[] bucketElementCounts = new int[10];        for (int i =0; i < arr.length;i ++){
               int digitOfElement = arr[i] % 10;            //获得每一个数个位数上的值            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[i];            //bucket[桶序号][bucketElementCount[桶序号]] = 值            //bucket[桶序号][在桶里面的索引] = 值            //bucketElementCount[桶序号]:表示对应桶的索引            bucketElementCounts[digitOfElement] ++;        }        //下一阶段,将所有桶中的数据放到原始数组中去,遍历所有的桶        int index = 0;        for (int i = 0;i < 10;i ++){
               //i代表桶的序号            //判定该桶是否为空在进行遍历            if (bucketElementCounts[i] != 0){
                   //bucketElementCounts表示每个桶中的元素索引,对不为0的桶进行索引                for (int j = 0;j < bucketElementCounts[i];j ++){
                       //j表示对应桶中的元素索引                    arr[index] = bucket[i][j];                    index ++;                    //复制元素两步走,同位相复制,同时移位.                }            }            bucketElementCounts[i] = 0;            //每一次循环结束之后都要将各个桶的索引清零        }        System.out.println(Arrays.toString(arr));

两个过程：

第二次循环：

index = 0;        for(int j = 0;j < arr.length;j ++){
               int digitOfElements =arr[j] / 10 % 10 ;            //获得十位数的好方法arr[j] / 10 % 10;干掉各位,十位变成个位            bucket[digitOfElements][bucketElementCounts[digitOfElements]] = arr[j];            bucketElementCounts[digitOfElements] ++;        }        //下一步遍历所有的桶,进行输出        //索引置零        for(int i = 0;i < 10;i ++){
               //遍历十个桶,然后判断是否为空,如果为空那就不在遍历            if(bucketElementCounts[i] != 0){
                   //这里有一个问题,每一次重复执行装桶的操作前,应该把各个桶的计量数清零                for (int j = 0;j < bucketElementCounts[i];j ++){
                       arr[index] = bucket[i][j];                    index ++;                }            }        }        System.out.println(Arrays.toString(arr));

提炼代码：

public static void radixsort(int[] arr) {
           int[][] bucket = new int[10][arr.length];        int[] bucketElementCounts = new int[10];        //通过观察发现,根据索要排序的数据的最大值的位数不同,我们对应进行的大循环次数不同        //找到最大的数字        int max = arr[0];        for (int i = 1; i < arr.length; i++) {
               if (max < arr[i]) {
                   max = arr[i];            }        }        //确定max的位数,从而确定循环的次数        int maxLength = (max + "").length();        //这个方法可以适当的积累一下,这就很巧妙了,将数字转成字符串直接运算获得        for (int m = 0, n = 1; m < maxLength; m++, n *= 10) {
               for (int i = 0; i < arr.length; i++) {
                   int digitOfElement = arr[i] / n % 10;                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[i];                bucketElementCounts[digitOfElement]++;            }            //下一阶段,将所有桶中的数据放到原始数组中去,遍历所有的桶            int index = 0;            for (int i = 0; i < 10; i++) {
                   //i代表桶的序号                //判定该桶是否为空在进行遍历                if (bucketElementCounts[i] != 0) {
                       //bucketElementCounts表示每个桶中的元素索引,对不为0的桶进行索引                    for (int j = 0; j < bucketElementCounts[i]; j++) {
                           //j表示对应桶中的元素索引                        arr[index] = bucket[i][j];                        index++;                        //复制元素两步走,同位相复制,同时移位.                    }                }                bucketElementCounts[i] = 0;            }        }    }

注意：

• 基数排序是典型的以空间换时间的算法，占用内存极其大，当对海量数据排序时，极其容易造成OutOfMemoryError，内存溢出，

  内存计算方式：n（需要计算的数字的方位）* 11（算上桶，算上原始数    组，总共有十一个）*4（int型是4个字节）/1024/1024

• 基数排序是稳定的，即按照排序标准，相同的两个对象顺序不会改变，仍旧按照原序列出现

• 基数排序不能够处理负数的情况，处理复数涉及到取绝对值和反转操作，若是不加会出现栈溢出

分析与总结：

1. 获取数字长度的便捷方式： 将之转化为字符串，直接String的方法`

int maxLength = (max + "").length();

2. n次方运算的诀窍，运用for循环，输出依次为1，10，100等10的若干次方

for(int i = 1;i < 3;i *= 10){
         System.out.println(i); }

3. 最大的数是几位数就有几次大循环，每一次大循环要求的对应数位上的值是不同的，所以关于求对应数位上的数的公式中的n次方的循环应该跟随最大的循环。每次循环结束，index原始数组恢复索引都要清零，每个桶的坐标都归零
4. 整个过程无非就是两个过程的循环，入桶和出桶，而入桶和出桶的关键在于对索引坐标的处理。

转载地址：http://wqgpb.baihongyu.com/