Java实现基数排序

基数排序的思路就是从整数的最后一位开始向前面根据基数进行分组的一种排序算法。
eg: 示例数组 int[] arr={3,23,41,5,22,1,31,1,6,71};

1. 首先从最后一位开始按0-9进行分组
   以1结尾的有41,1,31,1,71
   以2结尾的有22
   以3结尾的有3,23
   以5结尾的有5
   以6结尾的有6
   其他的没有该据
   即现在的桶里面的数据如下
   
   现在的数组顺序是 {41 1 31 1 71 22 3 23 5 6}
2. 根据数字的倒查第二位开始分组
   以为倒查第二位的有1 1 3 5 6
   以1倒查第二位的有
   以2倒查第二位的有22 23
   以3倒查第二位的有31
   以4倒查第二位的有41
   以7倒查第二位的有71
   此时的数组顺序是{1 1 3 5 6 22 23 31 41 71} 排序完成

Java代码如下

public class RadixSort {
    public static void main(String[] args) {
        int[] array={3,23,41,5,22,1,31,1,6,71};
        List<Integer> list = sortRadix(array);
        System.out.println(list);
    }

    //找到最大的数字
    public static int maxDigit(int[] array){
        if(array.length!=0){
            int maxNum=array[0];
            for(int i=1;i<array.length;i++){
                if(array[i]>maxNum){
                    maxNum=array[i];
                }
            }
            return maxNum;
        }else{
            throw new NullPointerException("数组为空");
        }
    }
    //最多位数
    public static int maxCapacity(int number){
        int cnt=0;
        while(number!=0){
            number=number/10;
            cnt++;
        }
        return cnt;
    }

    //返回数字某一位的数字
    public static int returnNum(int pos,int number){
        int digits = maxCapacity(number);//数字的位数
        int i=0;
        int temp=0;
        while(i<=pos){
            temp=number%10;
            number=number/10;
            i++;
            if(i>digits){//如果此时的下标超过数字的位数返回0
                return 0;
            }
        }
        return temp;
    }

    //基数排序
    public static List<Integer> sortRadix(int[] num){
        List<Integer> list[]= new ArrayList[10];//创建10个容器
        List<Integer> sorted = new ArrayList<>();
        for(int i=0;i<10;i++){//初始化容器
            list[i]= new ArrayList<>();
        }
        int maxnum = maxDigit(num);//最大的数字
        int maxcapacity = maxCapacity(maxnum);//最大的容量

        for(int i=0;i<10;i++){
            int digit = returnNum(0,num[i]);
            list[digit].add(num[i]);
        }//添加到容器里面

        //再操作列表里面的值
        for(int i =1;i<maxcapacity;i++){
            for(int j=0;j<10;j++){
                if(list[j].size()!=0){
                    //再次进行操作列表
                    int cnt=list[j].size();
                    int k=0;
                    while(k<cnt){
                        int temp = list[j].remove(0);//头节点
                        int digit = returnNum(i,temp);
                        list[digit].add(temp);
                        k++;
                    }
                }
            }
        }
        for(int j=0;j<10;j++){
            if(list[j].size()!=0){
              sorted.addAll(list[j]);
            }
        }
        return sorted;
    }
}