基数排序法

package com.company;

public class RadixSort {
    /**
     * 基数排序其实就是哈希排序
     * 桶排序的思想，它的关键思
     * 想就是空间换时间，这是一
     * 种常用的算法思想。
     * 空间就是你需要一个二维数组
     * 1维是从0到9这10个数字。
     * 2维个数是数组的长度。
     * 依次按照个位、十位、百位上
     * 面的数字为标准，只要和空间
     * 数组一维上面的index相同就
     * 应该被分配到同一组上去。
     * @param sourceArray
     */
    static public void radixSort0(int[] sourceArray) {
        for (int element:sourceArray) {
            if (element < 0) {
                System.out.println("错误!基数排序只适用于自然数!");
                return;
            }
        }
        int arrayLength = sourceArray.length;
        //创建临时存储空间
        int[][] tempArray = new int[10][arrayLength];
        //桶中的下标指针，默认为-1
        int[] pointerArray = new int[10];
        //为了更加通用一些我还是显示赋值吧
        for (int counter = 0;counter < 10;counter++)pointerArray[counter] = -1;
        //用来表示待比较的数的最大位数，默认值为0.
        int maxDigit = 1;
        int maxValue = sourceArray[0];
        //首先获取最大的值，并且创建位数数组。
        for (int counter = 0;counter < arrayLength;counter++) {
            if (sourceArray[counter] > maxValue)maxValue = sourceArray[counter];
        }
        while (maxValue / 10 != 0) {
            maxDigit++;
            maxValue /= 10;
        }
        //创建位数数组
        int[] digitArray = new int[maxDigit];
        digitArray[0] = 1;
        for (int counter = 1;counter < maxDigit;counter++)
            digitArray[counter] = 10 * digitArray[counter - 1];
        for (int digit = 0;digit < maxDigit;digit++) {
            for (int counter = 0;counter < arrayLength;counter++) {
                //获取某一位的值
                int digitNumber = (sourceArray[counter] / digitArray[digit]) % 10;
                tempArray[digitNumber][++pointerArray[digitNumber]] = sourceArray[counter];
            }
            //打印桶中的状态
            for (int counter = 0;counter < 10;counter++) {
                System.out.print("第" + (counter + 1) + "桶:");
                for (int counter0 = 0;counter0 <= pointerArray[counter];counter0++) {
                    System.out.print(tempArray[counter][counter0] + " ");
                }
                for (int counter1 = pointerArray[counter];counter1 < arrayLength;counter1++) {
                    System.out.print("- ");
                }
                System.out.println();
            }
            System.out.println("第" + (digit + 1) + "次装桶状态展示完毕");
            //至此一趟结束，此时需要把桶中的元素都取出来
            int sourceArrayPointer = 0;
            for (int counter = 0;counter < 10;counter++) {
                if (pointerArray[counter] > -1) {
                    //桶中的最高index数
                    int maxIndex = pointerArray[counter];
                    while (pointerArray[counter] > -1) {
                        sourceArray[sourceArrayPointer++] = tempArray[counter][maxIndex - pointerArray[counter]];
                        pointerArray[counter]--;
                    }
                }
            }
            System.out.print("出桶以后:");
            for (int element:sourceArray)System.out.print(element + " ");
            System.out.println("出桶以后状态展示完毕\n");
        }
    }
}