算法学习记录010

package com.study.data.structures.sort;

import java.util.Arrays;



public class RadixSort {

    public static void main(String[] args) {
        int[] arr = {43, 986, 7, 21, 591, 87};
//        radixSortDeduction(arr);
        int[] arrays = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arrays[i] = (int) (Math.random() * 8000000);
        }
        long startTime = System.currentTimeMillis();
        radixSort(arrays);
        long endTime = System.currentTimeMillis();
        System.out.println(endTime - startTime);
    }

    private static void radixSort(int[] arr) {
        //定义一个二维数组,使用arr.length是因为实在无法确定，每个一维数组会装多少元素，所以就去最大值
        int[][] radixTemp = new int[10][arr.length];
        //用于记录每个一维数组添加数据的个数
        int[] radixCount = new int[10];
        //先获取待排序数组中的最大数值，用以确定外层循环需要多少次
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        System.out.println(max+"");

        int maxLength = (max + "").length();
        int index = 0;
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            for (int j = 0; j < arr.length; j++) {
                int num = arr[j];
                int digit = num / n % 10;
                //获得下标为digit的数组
                int[] currentArr = radixTemp[digit];
                //往下标为digit的数组中添加数据
                currentArr[radixCount[digit]++] = num;
            }
            index = 0;
            for (int k = 0; k < radixCount.length; k++) {
                int count = radixCount[k];
                if (count != 0) {
                    for (int g = 0; g < count; g++) {
                        arr[index++] = radixTemp[k][g];
                    }
                    radixCount[k] = 0;
                }
            }

//            System.out.println("第" + i + "轮：：" + Arrays.toString(arr));
        }

    }

    private static void radixSortDeduction(int[] arr) {
        //定义一个二维数组,使用arr.length是因为实在无法确定，每个一维数组会装多少元素，所以就去最大值
        int[][] radixTemp = new int[10][arr.length];
        //用于记录每个一维数组添加数据的个数
        int[] radixCount = new int[10];
        //第一轮
        for (int i = 0; i < arr.length; i++) {
            int num = arr[i];
            int singleDigit = num % 10;
            int[] currentArr = radixTemp[singleDigit];
            currentArr[radixCount[singleDigit]++] = num;
        }
        int index = 0;
        for (int i = 0; i < radixCount.length; i++) {
            int count = radixCount[i];
            if (count != 0) {
                for (int j = 0; j < count; j++) {
                    arr[index++] = radixTemp[i][j];
                }
                radixCount[i] = 0;
            }
        }

        System.out.println("第一轮：：" + Arrays.toString(arr));


        //第二轮
        for (int i = 0; i < arr.length; i++) {
            int num = arr[i];
            int singleDigit = num / 10 % 10;
            int[] currentArr = radixTemp[singleDigit];
            currentArr[radixCount[singleDigit]++] = num;
        }
        index = 0;
        for (int i = 0; i < radixCount.length; i++) {
            int count = radixCount[i];
            if (count != 0) {
                for (int j = 0; j < count; j++) {
                    arr[index++] = radixTemp[i][j];
                }
                radixCount[i] = 0;
            }
        }

        System.out.println("第二轮：：" + Arrays.toString(arr));

        //第三轮
        for (int i = 0; i < arr.length; i++) {
            int num = arr[i];
            int singleDigit = num / 100 % 10;
            int[] currentArr = radixTemp[singleDigit];
            currentArr[radixCount[singleDigit]++] = num;
        }
        index = 0;
        for (int i = 0; i < radixCount.length; i++) {
            int count = radixCount[i];
            if (count != 0) {
                for (int j = 0; j < count; j++) {
                    arr[index++] = radixTemp[i][j];
                }
                radixCount[i] = 0;
            }
        }

        System.out.println("第三轮：：" + Arrays.toString(arr));
    }
}