Please enable Javascript to view the contents

排序算法之基数排序

 ·  ☕ 2 分钟

基数排序算法很特殊,它不需要直接对元素进行相互比较,也不需要将元素相互交换,你需要做的就是对元素进行“分类”。

将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

一、排序步骤

  1. 取得数组中的最大数,并取得位数;
  2. arr为原始数组,从最低位开始取每个位组成radix数组;
  3. 对radix进行计数排序(利用计数排序适用于小范围数的特点);

二、动画演示

radix_sort

三、代码实现

 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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
package com.whoismy8023.learning.sort;

import java.util.Arrays;

/**
 * Created by SPPan on 2019/9/11.
 * <p>
 * 基数排序
 */
public class RadixSortLearning {

    public static void main(String[] args) {
        int[] arr = {1, 9, 2, 8, 3, 6, 5, 4};
        System.out.printf("排序前:%s \n", Arrays.toString(arr));
        radixSort(arr);
        System.out.printf("排序后:%s \n", Arrays.toString(arr));
    }

    private static void radixSort(int[] arr) {
        // 得到数组中最大的数的位数,假设第一数就是最大数
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        // 得到最大数是几位数
        int maxLength = String.valueOf(max).length();
        // 定义一个二维数组,表示 10 个桶, 每个桶就是一个一维数组
        // 说明
        // 1. 二维数组包含 10 个一维数组
        // 2. 为了防止在放入数的时候,数据溢出,则每个一维数组(桶),大小定为 arr.length
        // 3. 名明确,基数排序是使用空间换时间的经典算法
        int[][] bucket = new int[10][arr.length];
        // 为了记录每个桶中,实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数
        // 可以这里理解
        // 比如:bucketElementCounts[0] , 记录的就是 bucket[0] 桶的放入数据个数
        int[] bucketElementCounts = new int[10];
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            // (针对每个元素的对应位进行排序处理), 第一次是个位,第二次是十位,第三次是百位..
            for (int j = 0; j < arr.length; j++) {
                // 取出每个元素的对应位的值
                int digitOfElement = arr[j] / n % 10;
                // 放入到对应的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }
            // 按照这个桶的顺序(一维数组的下标依次取出数据,放入原来数组)
            int index = 0;
            // 遍历每一桶,并将桶中是数据,放入到原数组
            for (int k = 0; k < bucketElementCounts.length; k++) {
                // 如果桶中,有数据,我们才放入到原数组
                if (bucketElementCounts[k] != 0) {
                    // 循环该桶即第 k 个桶(即第 k 个一维数组), 放入
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        // 取出元素放入到 arr
                        arr[index++] = bucket[k][l];
                    }
                }
                // 第 i+1 轮处理后,需要将每个 bucketElementCounts[k] = 0 !!!!
                bucketElementCounts[k] = 0;
            }
        }
    }
}

四、代码演示结果

1
2
排序前:[1, 9, 2, 8, 3, 6, 5, 4] 
排序后:[1, 2, 3, 4, 5, 6, 8, 9] 
目录