package com.rao.sort;

import java.util.*;

/**

 * @author Srao

 * @className RadioSort

 * @date 2019/12/10 18:17

 * @package com.rao.sort

 * @Description 基数排序

 */

public class RadioSort {

    /**

     * 基数排序

     * @param arr

     * @return

     */

    public static int[] radioSort(int[] arr){

        //1.找出最大值

        int n = arr.length;

        int max = arr[];

        for (int i = ; i < n; i++) {

            if (max < arr[i]){

                max = arr[i];

            }

        }

        //2.求出对大值的位数

        int num = ;

        while (max /  > ){

            num++;

            max /= ;

        }

        //3.创建桶

        List<LinkedList<Integer>> bucketList = new ArrayList<>();

        //4.初始化桶

        for (int i = ; i < ; i++) {

            bucketList.add(new LinkedList<>());

        }

        //5.把每个数放到对应的桶当中

        for (int i = ; i <= num; i++){

            for (int j = ; j < n; j++) {

                int index = (int) ((arr[j]/Math.pow(, i-)) % );

                bucketList.get(index).add(arr[j]);

            }

            //6.把桶中的数输出到原数组

            int k = ;

            for (int j = ; j < ; j++){

                for (Integer integer : bucketList.get(j)) {

                    arr[k] = integer;

                    k++;

                }

                //清除桶中的元素

                bucketList.get(j).clear();

            }

        }

    return arr;

    }

    public static void main(String[] args) {

        int[] arr = new int[]{,,,,,,,};

        System.out.println(Arrays.toString(arr));

        arr = radioSort(arr);

        System.out.println(Arrays.toString(arr));

    }

}