排序算法-基数排序

算法思想

完整代码实现：

package com.sort;

import java.util.LinkedList;
import java.util.Queue;

public class BaseSort {
    public static void main(String[] args) {
        int[] nums = {3,89,4,53,6,825,900,0,1000,53};
        basesort(nums,nums.length);
        System.out.println("最终输出结果:");
        for(int num:nums){
            System.out.print(num+" ");
        }


    }
    public static void basesort(int[] nums,int len){
        int max = 0; //寻找待排序数组中的最大值，以确定位数d
        for(int num:nums)
            max = Math.max(max,num);
        int d = GetNum_d(max);
        //建立分配和收集队列,十进制数总共需要0~9，十个队列
        Queue<Integer>[] queues = new Queue[10];
        //初始化这10个队列
        for(int i=0;i<10;++i){
            queues[i] = new LinkedList<>();
        }
        //根据位数d来确定 分配和收集 的趟数
        for(int i=0;i<d;++i){
            //分配
            for(int num:nums){
                int temp = num;
                num /= (int)Math.pow(10,i);
                queues[num%10].offer(temp);
            }
            //收集,降序排列所以从最低位开始收集
            int k = 0;
            for(int j=0;j<10;++j){
                while(!queues[j].isEmpty() && k<len){
                    nums[k++] = queues[j].poll();
                }
            }
            System.out.printf("第 %d 趟收集之后的结果:\n",i);
            for(int num:nums){
                System.out.print(num+" ");
            }
            System.out.println();
        }
    }
    public static int GetNum_d(int num){
        int d = 1;
        while(num/10!=0){
            num /=10;
            d++;
        }
        return d;
    }

}

输出结果：