简介

基数排序属于“分配式排序”，又称“桶子法”，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为对数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

中文名 基数排序 外文名 Radix sort 别 名 “桶子法”

举例说明

1。 假设原来有一串数值: 73, 22, 93, 43, 55, 14, 28, 65, 39, 81

首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：

0

1 81

2 22

3 73 93 43

4 14

5 55 65

6

7

8 28

9 39

2。 接下来将这些桶子中的数值重新串接起来，成为以下的数列：

81, 22, 73, 93, 43, 14, 55, 65, 28, 39

接着再进行一次分配，这次是根据十位数来分配：

0

1 14

2 22 28

3 39

4 43

5 55

6 65

7 73

8 81

9 93

3。 接下来将这些桶子中的数值重新串接起来，成为以下的数列：

14, 22, 28, 39, 43, 55, 65, 73, 81, 93

这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。

代码实现

 package com.zyp.sort;

import java.util.Arrays;

/**
 * 基数排序
 * @author zyp
 * @create 2022/2/21
 */public class RadixSort {
    public static void main(String[] args) {
        //待排序数组
        int[] array = new int[]{73, 22, 93, 43, 55, 14, 28, 65, 39, 81};
        /**
         * 先找到数据中的最大值
         */        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (max < array[i]) {
                max = array[i];
            }
        }
        /**
         * 声明一个长度为10的二维数组
         * 这10个二维数组代表下标为0-9的桶。用于储存个位、十位、百位对应的数组
         */        int[][] blackArray = new int[10][array.length];

        //声明一个数组，用于记录二维数组中的数据的个数
        int[] count = new int[10];
        
        //用于获取待排序中元素的个位、十位、百位、千位...的辅助变量
        int n = 1;
        //最大值有多少位就要进行多少次
        for (int i = 0; i < (max + "").length(); i++) {
            //将数组中的数据放入二维数组中（先从个位开始）
            for (int j = 0; j < array.length; j++) {
                int index = array[j] / n % 10;
                blackArray[index][count[index]] = array[j];
                count[index]++;
            }
            int arrayIndex = 0;
            //将二维数组中的数据按照顺序放回到数组中
            for(int k = 0;k < blackArray.length;k++){
                if(count[k] != 0) {
                    for (int x = 0; x < count[k]; x++) {
                        array[arrayIndex] = blackArray[k][x];
                        arrayIndex++;
                    }
                    count[k] = 0;
                }
            }
            n = n * 10;
            System.out.println("第"+(i+1)+"轮之后的结果:"+Arrays.toString(array));
        }
    }
}
  

图片说明

帮助理解