基数排序

分析

基数排序(Radix Sort)是桶排序的扩展，它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。
具体做法是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

代码

package 算法;

import java.util.Arrays;

public class 基数排序 {
    public static void main(String[] args) {
        int[] arr = {53,3,542,748,1114,214,1};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void radixSort(int[] arr){
        //设置二维数组作为桶
        int[][] bucket = new int[10][arr.length];
        //设置每个桶的指针
        int[] bucketIndex = new int[10];
        int max = Integer.MIN_VALUE;
        for (int i : arr) {
            if(i>max){
                max = i;
            }
        }
        int len = (max+"").length();
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < arr.length; j++) {
                //算出这个数在哪个桶
                int numIndex = (arr[j]/((int)Math.pow(10, i)))%10;
                //将这个数放入桶中
                bucket[numIndex][bucketIndex[numIndex]]=arr[j];
                bucketIndex[numIndex]++;
            }
            int index = 0;
            for (int k = 0; k < bucketIndex.length; k++) {
                if(bucketIndex[k]!=0){
                    for (int l = 0; l <bucketIndex[k] ; l++) {
                        arr[index++] = bucket[k][l];
                    }
                }
                bucketIndex[k] = 0;
            }
        }

    }
}