基数排序（桶排序） 2022.01.04

基数排序（桶排序） 2022.01.04

基数排序（桶排序）的基本思想：先按个位数的大小给数组排序，再按十位数的大小给数组排序，以此类推，直到数组中最大位数的最大位被排序完，此时数组有序。在排序的过程中需要创建二维数组，所以基数排序（桶排序）是典型的以空间换时间的算法。

基数排序（桶排序）执行结果如图：

基数排序（桶排序）代码如下：

package DataStructures.sort;

import java.util.Arrays;


public class RadixSort {
    public static void main(String[] args) {
        int[] nums = {53,3,542,748,14,214};
        System.out.println("初始数组为："+Arrays.toString(nums));
        radixSort(nums);
    }

    //
    public static void radixSort( int[] nums ){
        //先找最大位数
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if( nums[i] > max ){
                max = nums[i];
            }
        }
        int maxLength = (max+"").length();

        int[][] bucket = new int[10][nums.length];

        int[] bucketElementCounts = new int[10];

        //开始排序
        for( int i = 0, n = 1; i < maxLength; i++, n *= 10 ){
            //将每个数依次放入桶中
            for( int j = 0; j < nums.length; j++ ){
                int digitOfElement = nums[j] / n % 10;
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = nums[j];
                bucketElementCounts[digitOfElement]++;
            }
            //将桶中的数依次放入数组
            int index = 0;
            for( int k = 0; k < bucketElementCounts.length; k++){
                if( bucketElementCounts[k] != 0 ){
                    for( int l = 0; l < bucketElementCounts[k]; l++){
                        nums[index++] = bucket[k][l];
                    }
                }
                bucketElementCounts[k] = 0;
            }
            System.out.println("第"+(i+1)+"轮基数排序："+ Arrays.toString(nums));
        }
    }
}