package com.jiucaiyuan.net.algrithm.sort;



import java.net.InetSocketAddress;



/**

 * <pre>

 * 基数排序

 *  根据数据特点进行排序，而非基于比较

 * 	 时间复杂度O(N*logN)  空间复杂度O(1)

 * </pre>

 * Created by jiucaiyuan on 2022/4/1.

 */

public class RadixSort {

    public static void radixSort(int[] arr) {

        if (arr == null || arr.length < 2) {

            return;

        }

        radixSort(arr, 0, arr.length - 1, maxBits(arr));

    }



    /**

     * 找出数组中最大数字的宽度

     *

     * @param arr

     * @return

     */

    public static int maxBits(int[] arr) {

        int max = Integer.MIN_VALUE;

        //找到最大的数

        for (int i : arr) {

            max = Math.max(i, max);

        }

        //计算宽度

        int result = 0;

        while (max != 0) {

            result++;

            max /= 10;

        }

        return result;

    }



    /**

     * 针对arr[l~r]进行排序

     *

     * @param arr   待排序数组

     * @param l     左侧下标

     * @param r     右侧下标

     * @param digit l到r之间最大数字的字符数（宽度）

     */

    public static void radixSort(int[] arr, int l, int r, int digit) {

        final int radix = 10;

        int i = 0, j = 0;

        //有多少个数据，就准备多少个辅助空间

        int[] bucket = new int[r - l + 1];

        //有多少位，就进出几次桶

        for (int d = 1; d <= digit; d++) {

            //10个空间

            //count[0],当前位置（d位）是0的数字有多少个

            //count[1],当前位置（d位）是0和1的数字有多少个

            //count[2],当前位置（d位）是0、1和2的数字有多少个

            //count[3],当前位置（d位）是0、1、2和3的数字有多少个

            //  ...

            //count[i],当前位置（d位）是0~i的数字有多少个

            //count[0~9]

            int[] count = new int[radix];

            //累计d位置出现j的次数

            for (i = l; i <= r; i++) {

                j = getDigit(arr[i], d);

                count[j]++;

            }

            //count数组转化为count[i]为所有<=i的数字之和，即小于等于i的个数之和

            //把count处理成前缀和

            for (i = 1; i < radix; i++) {

                count[i] = count[i - 1] + count[i];

            }

            //把i位置上的数，放到d位置上的数字及之前出现的次数-1的辅助空间中

            //等于操作了入桶和出桶操作

            for (i = r; i >= l; i--) {

                j = getDigit(arr[i], d);

                bucket[--count[j]] = arr[i];

            }

            //局部处理完的数组拷贝回原数组

            for (i = l, j = 0; i <= r; i++, j++) {

                arr[i] = bucket[j];

            }

            print(bucket);

        }

    }



    /**

     * 返回数字num倒数第d位置的数字

     * @param num

     * @param d

     * @return

     */

    private static int getDigit(int num, int d) {

        return (num / ((int) Math.pow(10, d - 1))) % 10;

    }



    public static void main(String[] args) {

        int[] arr = {12, 15, 63, 102, 32, 53, 908};

        radixSort(arr);

        System.out.println("-------------");

        print(arr);

    }



    private static void print(int[] arr) {

        if (arr == null) {

            return;

        }

        for (int a : arr) {

            System.out.print(a + "\t");

        }

        System.out.println();

    }

}