package com.lxf.sort;

import java.util.Arrays;
import java.util.Random;

public class BaseSort {
    public static void main(String[] args) {
        //获取一个数字字符串
        StringBuilder stringBuilder = new StringBuilder();
        Random random = new Random();
        for (int i = 0; i < 100000; i++) {
            stringBuilder.append(random.nextInt(500)+",");
        }
        //去掉最后一个,
        stringBuilder.setLength(stringBuilder.length()-1);
        //获取整数数组
        String[] splits= stringBuilder.toString().split(",");
        int[] nums = Arrays.stream(splits).mapToInt(Integer::valueOf).toArray();
        //获取开始时间
        long  start = System.currentTimeMillis();
        System.out.println("start = " + start);
        //基数排序算法
        sort(nums);
        //获取执行完的时间
        long end = System.currentTimeMillis();
        System.out.println("end = " + end);
        //计算执行时间
        long sub=end-start;
        System.out.println("花费时间="+sub);

        //三次测试：94ms 84ms 50ms
    }
    public static void sort(int[] arr){
        //如果数组大小小于等于1直接返回
        if(arr.length<=1) {return;}
        //取得数组中最大的数
        int max=0;
        for (int i=0;i<arr.length;i++){
            if(max<arr[i]){
                max=arr[i];
            }
        }
        //取得最大数的位数
        int maxDight=1;
        while (max/10>0){
            maxDight++;
            max=max/10;
        }
        //申请一个桶空间
        int[][] buckets=new int[10][arr.length];
        int base=10;

        //从低位到高位，对每一位遍历，将所有的元素分配到桶中
        for(int i=0;i<maxDight;i++){
            //存储各个桶中存储元素的数量
            int[] bktLen=new int[10];

            //分配：按位将所有的元素分配到桶中
            for(int j=0;j<arr.length;j++){
                //获取当前位数字大小
                int whichBucket=(arr[j]%base)/(base/10);
                //分配进对应数字大小的桶中
                buckets[whichBucket][bktLen[whichBucket]]=arr[j];
                //将每个桶的记录数量加一
                bktLen[whichBucket]++;
            }

            //收集：从低位到高位将不同桶的数据挨个捞出来，为下一轮高位排序做准备
            int k=0;
            for(int b=0;b<buckets.length;b++){
                for (int p=0;p<bktLen[b];p++){
                    arr[k++]=buckets[b][p];
                }
            }
            base*=10;
        }
    }
}