简介

        基数排序（radix sort）属于 “分配式排序”（distribution sort），又称 “桶子法”（bucket sort）或 bin sort，

        顾名思义，它是通过键值的部分信息，将要排序的元素分配至某些"桶"中，以达到排序的作用，

        在某些时候，基数排序法的效率高于其它的稳定性排序法。

基本思想

排序实例

1、举个栗子，假设原来有一串数值为：｛73, 22, 93, 43, 55, 14, 28, 65, 39, 81｝。

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

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

｛81，22，73，93，43，14，55，65，28，39｝

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

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

｛14，22，28，39，43，55，65，73，81，93｝

6、按这样的操作循环往复，直到按所有值的最高位排序完，那么整个序列就排序完成了。

总结

        对序列的所有数据，从最低位开始，每次进行一轮排序；

        每一轮排序完成后，将序列合并；

        然后按新序列的高一位继续排序，直到排完最高位，整个序列排序完成。

排序过程

        此处排序数据：{3221, 10, 9680, 577, 9420, 4793, 2030, 82, 743}

代码实现

import java.util.ArrayList;

/**
 * 基数排序
 * @Author  distance
 */
public class RadixSort {

    public static void sort(int[] num) {
        int max = Integer.MIN_VALUE; // 找最大值
        for (int i = 0; i < num.length; i++) {
            if (num[i] > max) {
                max = num[i];
            }
        }

        int maxLen = 1; // 求最大值有几位
        max /= 10;
        while (max > 0) {
            maxLen ++;
            max /= 10;
        }

        ArrayList<ArrayList<Integer>> bucket = new ArrayList<>(10);// 0 ~ 9 的桶
        for (int i = 0; i < 10; i++) {
            bucket.add(new ArrayList<Integer>());
        }

        int temp, index;
        for (int base = 0; base < maxLen; base++) { // 从 0 ~ maxLen-1 位
            for (int i = 0; i < num.length; i++) {
                temp = get(num[i],base); // 求 num[i] ，base 位上的数是多少

//                System.out.print(temp + " ");
                bucket.get(temp).add(num[i]); // 根据当前位的值，放入桶内
            }
//            System.out.println();

            index = 0; // 按该位排完，重新拼接起来，加回原数组
            for (int i = 0; i < 10; i++) {
                for (int j = 0; j < bucket.get(i).size(); j++) {
                    num[index++] = bucket.get(i).get(j);
                }

                bucket.get(i).clear(); // 添加完回去之后，清空 bucket，准备下一轮排序
            }

        }
    }

    // 求 num ，base 位上的数是多少
    public static int get(int num,int index) {
        int bas = 1;
        for (int i = 0; i < index; i++) {
            bas *= 10;
        }
        // 写 long 防止出现 Integer.MAX_VALUE 出错的情况
        return (int) (num % (bas * 10L) / bas);
    }

    public static void main(String[] args) {

        int[] num = {3221, 10, 9680, 577, 9420, 4793, 2030, 82, 743};

        RadixSort.sort(num);

        for (int i = 0; i < num.length; i++) {
            System.out.print(num[i] + " ");
        }
    }
}

算法分析

时间复杂度

        假设待排序列为 \(n\) 个记录，待排序列最大位数为 \(d\) ，每一位数的取值范围为 \(radix\)（一般是 0~9），

        则进行链式基数排序的时间复杂度为 \(O(d*(n+radix))\)，其中，一趟分配时间复杂度为 \(O(n)\)，

        一趟收集时间复杂度为 \(O(radix)\)，共进行 d 趟分配和收集。

        所以基数排序的时间复杂度为 O(d(n+radix))，其中 d 为最大位数，radix 为每一位的范围。

算法稳定性

        基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。

        基数排序基于分别排序，分别收集，所以其是稳定的排序算法。

        所以，基数排序是一种稳定的排序算法。

排序算法之基数排序