（十三）Java算法：基数排序（详细图解）

一、前言

1.1、概念

   基数排序：（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，从而达到排序的作用，基数排序法是属于稳定性的排序。

1.2、计数排序 vs 桶排序 vs 基数排序

• 计数排序：每个桶只存储单一键值
• 桶排序：每个桶存储一定范围的数值
• 基数排序：根据键值的每位数字来分配桶

1.3、算法步骤

• 找出待排序的数组中的最大元素max
• 根据指定的桶数创建桶，本文使用的桶是LinkedList结构
• 从个位数开始到最高位进行遍历：num/ divider % 10 = 1，divider 取值为[1,10,100,100,…]
• 遍历数组中每一个元素，先进行分类，然后进行收集，分类就是按位放到对应的桶中，比如个位、十位、百位等（只看指定的位（个位、十位、百位等），如果此位没有数据则以0填充，比如8，按十位分类，那么就是08，放0号桶）
• 收集就是把桶的数据取出来放到我们的数组中，完成排序

   当然算法也可以对字母类排序，本文主要是对数字排序，大家比较好理解。

二、maven依赖

pom.xml

<dependencies>
    <dependency>
        <groupId>org.springframework.bootgroupId>
        <artifactId>spring-boot-starterartifactId>
        <version>2.6.0version>
    dependency>

    <dependency>
        <groupId>org.projectlombokgroupId>
        <artifactId>lombokartifactId>
        <version>1.16.14version>
    dependency>
dependencies>
1
2
3
4
5
6
7
8
9
10
11
12
13

三、流程解析

  假设我们要排序的数据是：10, 19, 32, 200, 23, 22, 8, 12, 9, 108

3.1、个位数排序

  

3.2、十位数排序

  

3.3、百位数排序

  

四、编码实现

/**
 * 基数排序
 *
 * @param arr
 */
public static void radixSort(int[] arr) {
    // 初始化最大值
    int max = Integer.MIN_VALUE;
    // 找出最大值
    for (int num : arr) {
        max = Math.max(max, num);
    }

    // 我们这里是数字，所以初始化10个空间，采用LinkedList
    LinkedList<Integer>[] list = new LinkedList[10];
    for (int i = 0; i < 10; i++) {
        list[i] = new LinkedList<>();// 确定桶的格式为ArrayList
    }

    // 个位数：123 / 1 % 10 = 3
    // 十位数：123 / 10 % 10 = 2
    // 百位数: 123 / 100 % 10 = 1
    for (int divider = 1; divider <= max; divider *= 10) {
        // 分类过程(比如个位、十位、百位等)
        for (int num : arr) {
            int no = num / divider % 10;
            list[no].offer(num);
        }
        log.info("分类结果为：{}", Arrays.asList(list));
        int index = 0; // 遍历arr原数组
        // 收集的过程
        for (LinkedList<Integer> linkedList : list) {
            while (!linkedList.isEmpty()) {
                arr[index++] = linkedList.poll();
            }
        }
        log.info("排序后结果为：{}", arr);
        log.info("---------------------------------");
    }
}

public static void main(String[] args) {
    int[] arr = {10, 19, 32, 200, 23, 22, 8, 12, 9, 108};
    log.info("要排序的数据为：{}", arr);
    radixSort(arr);
    log.info("基数排序的结果为：{}", arr);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

运行结果：

要排序的数据为：[10, 19, 32, 200, 23, 22, 8, 12, 9, 108]
分类结果为：[[10, 200], [], [32, 22, 12], [23], [], [], [], [], [8, 108], [19, 9]]
排序后结果为：[10, 200, 32, 22, 12, 23, 8, 108, 19, 9]
---------------------------------
分类结果为：[[200, 8, 108, 9], [10, 12, 19], [22, 23], [32], [], [], [], [], [], []]
排序后结果为：[200, 8, 108, 9, 10, 12, 19, 22, 23, 32]
---------------------------------
分类结果为：[[8, 9, 10, 12, 19, 22, 23, 32], [108], [200], [], [], [], [], [], [], []]
排序后结果为：[8, 9, 10, 12, 19, 22, 23, 32, 108, 200]
---------------------------------
基数排序的结果为：[8, 9, 10, 12, 19, 22, 23, 32, 108, 200]
1
2
3
4
5
6
7
8
9
10
11