[数据结构与算法]排序算法之基数排序

简介

????????基数排序（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 为每一位的范围。

算法稳定性

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

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

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