使用队列实现基数排序

基数排序：
排序方法：
第一步：设原来数组如下所示：2, 225,25,36,12,99,2,1,5, 5563, 12251
第二步：首先根据个位数的数值，遍历将它们分配至编号0到9的队列中
第三步：接下来将这些队列中的数值按先进先出的顺序重新串接起来。
第四步：持续进行第2，3步的动作直至最高位数为止，数组最终有序

public class RadixSort {

  public static void radixSort(int[] arr) {
        //找到数组中最大的数字，并判断是几位数字
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }

        int maxlength = Integer.toString(max).length();
        //定义10个临时队列,0~9各一个，可以在菜鸟教程学习到如何使用linkedlist实现队列
        Queue[] temp = new Queue[10];
        for (int i = 0; i < temp.length; i++) {
            temp[i] = new LinkedList<Integer>();
        }

        //根据最大位数，决定比较次数,第一次取数的个位比较排序，第二取数的十位比较排序，第三次取数的百位比较排序，以此类推
        for (int i = 0, n = 1; i < maxlength; i++, n *= 10) {
            //按每一个数字的当前位的大小进行排序
            for (int j = 0; j < arr.length; j++) {
                //求模得到数的个位，十位，百位的值
                int num = arr[j] / n % 10;
                //放入对应的临时队列
                temp[num].offer(arr[j]);
            }
            //该索引用于更新arr数组
            int index = 0;
            //再把每个队列的数字取出来
            for (int k = 0; k < temp.length; k++) {
                //当前遍历的队列不为空
                while (!temp[k].isEmpty()) {
                    arr[index] = (int) temp[k].poll();
                    index++;
                }
            }


        }
    }
}

测试：

public static void main(String[] args) {
    int arr[] = {2, 225,25,36,12,99,2,1,5, 5563, 12251};
     radixSort(arr);
    System.out.println(Arrays.toString(arr));
}

基数排序图解：


以此类推直到按最大数的位数排好序：