目录

基数排序

基本介绍

基数排序与其他排序方法不同,它不需要比较关键字的大小。它是根据关键字中各位(个十百千万)的值,通过对排序的N个元素进行若干趟“分配”与“收集”来实现排序的。

排序思想

我们知道,任何一个阿拉伯数,它的各个位数上的基数都是以0~9来表示的。所以我们不妨把0~9视为10个桶。我们先根据序列的个位数的数字来进行分类,将其分到指定的桶中。例如:R[0] = 50,个位数上是0,将这个数存入编号为0的桶中。分类后,我们在从各个桶中,将这些数按照从编号0到编号9的顺序依次将所有数取出来。这时,得到的序列就是个位数上呈递增趋势的序列。接下来,可以对十位数、百位数也按照这种方法进行排序,最后就能得到排序完成的序列。

代码实现

 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
    /**
     * 基数排序
     *
     * @param arr
     */
    public static void radixSort(int[] arr) {
        // 定义十个桶,用来表示个位/十位/百位/...,0-9 十种情况
        int[][] buckets = new int[10][arr.length];
        // 定义一个二维数组,用来表示各个桶的元素最大下标
        int[] indexOfBuckets = new int[10];
        // 遍历处理个位、十位、百位...情况,重排序原始数组
        for (int i = 0, n = 1; i < getMaxLength(arr); i++, n *= 10) {
            // 1. 遍历每个数,放在对应的桶中
            for (int j : arr) {
                // 取出所在位数对应的值
                int digital = (j / n) % 10;
                // 将数放在对应的桶中
                buckets[digital][indexOfBuckets[digital]] = j;
                // 桶下标+1
                indexOfBuckets[digital]++;
            }
            // 2. 遍历每个桶的元素,将数放到原始数组中
            int m = 0;
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < indexOfBuckets[j]; k++) {
                    arr[m++] = buckets[j][k];
                }
            }
            // 将每个桶的下标置0
            for (int j = 0; j < 10; j++) {
                indexOfBuckets[j] = 0;
            }
        }

    }