排序7-基数排序

基数排序

基数排序不需要对关键字进行比较，只需要对关键字进行分配和收集两种操作即可完成

package com.sort;

import java.util.Arrays;

//基数排序
public class Demo07 {

    public static void main(String[] args) {
        //通过分配在收集的方式进行排序
        int[] arr= {2,1,5,21,31,444,23,33,47,10,903,124,1000,987,100};
        sortArray(arr);
        System.out.println(Arrays.toString(arr));
    }


    private static void sortArray(int[] arr){
        //定义二维数组，放10个桶
        int[][] tempArr = new int[10][arr.length];
        //定义一个统计数组
        int[] counts= new int[10];
        //确定排序轮次：获取数组中的最大值
        int max=getMax(arr);
        int len = String.valueOf(max).length();
        for (int i = 0,n=1; i < len; i++,n*=10) {
            //获取每个位上的数
            for (int j = 0; j < arr.length; j++) {
                int ys=arr[j]/n%10;
                tempArr[ys][counts[ys]++]=arr[j];
            }
            //取出桶中元素
            int index = 0;
            for (int k = 0; k < counts.length; k++) {
                if(counts[k]!=0){
                    for (int h = 0; h < counts[k]; h++) {
                        //从桶中取出元素放回原数组
                        arr[index]=tempArr[k][h];
                        index++;
                    }
                    counts[k]=0;//清除上一次统计的个数
                }
            }
        }
    }

    private static int getMax(int[] arr) {
        int max = arr[0];
        for(int i=1;i<arr.length;i++){
            if(arr[i]>max){
                max=arr[i];
            }
        }
        return max;
    }

}

本文地址：https://blog.csdn.net/angel56789/article/details/111994483