基数排序（Radix Sort）

  基数排序是一种不在数据值本身之间比较的排序算法，而是通过数据按位数“切割”对比，从而实现排序的算法，所以基数排序也被认为是一种典型的非比较排序算法。在实际运用中，基数排序的使用场景不局限于整数，凡是整数可以表达的，或者有规律格式的字符串，都适用。
  基数排序的发明，据说是一位叫赫尔曼·霍尔瑞斯的老先贤基于打孔卡片制表机的使用，在1887年总结出来的。故此算法，至今已有一百三十多年，所谓源远绵长、历史悠久，妥妥的百年算法，脱发致敬。

基本思想

  基数排序是将所有数据元素数值看成长度统一的数位元素，短数位则前面补零；然后从最低位开始，依次进行排序；从低到高依次操作，直至最后，所有数据元素即可成为有序序列。

算法描述

1：取数据元素中最大值为位数样本，数位较短的前面补零（想象中）；
2：以数据的末位数值开始进行入桶操作；
3：从最低位至向高位逐次进行类2操作，直至所有数位遍历完成，即完成排序操作。

动图演示

代码实现

import java.util.Arrays;

/**
 * @author :Veiking
 * @version :2020年10月15日 
 * 说明 :基数排序算法
 */
public class RadixSort {
    /**
     * 基数排序
     * @param arrays
     * @return
     */
    public static int[] sort(int[] arrays) {
        // 求出待排数的最大元素
        int maxItem = arrays[0];
        for (int i = 1; i < arrays.length; i++) {
            if (maxItem < arrays[i]) {
                maxItem = arrays[i];
            }
        }
        // 根据最大元素得出其计算位数
        int size = String.valueOf(maxItem).length();
        // 由于我们是对数字序列进行排序，即准备0~9十个临时数字数组作为容器，用于基数排序
        // 因考虑到极端情况，数组的第二维度长度与数据样本等长，为arrays.length
        int[][] buckets = new int[10][arrays.length];
        // 用于记录bucket数组中每个桶内存的数据的数量
        int[] counts = new int[10];
        // 用于记录每个数比较位数的数值
        int num = 0;
        // 用于记录取的元素需要放的位置
        int index = 0;
        // 根据最大元素位数决定排序的操作次数，记为i，figure则用于计算数据位数值，个十百千万等
        for (int i = 0; i < size; i++) {
            int figure = (int) Math.pow(10, i);
            // 将样本按位数计算规则，入桶
            for (int j = 0; j < arrays.length; j++) {
                num = arrays[j] / figure % 10;// 取当前位数据值
                buckets[num][counts[num]] = arrays[j]; // 待排元素入桶
                counts[num]++; // 值为num的 bucket桶元素数量递加
            }
            // 从buckets中取元素重新放到原arrays数组中
            for (int j = 0; j < counts.length; j++) {
                // 逐个放回
                for (int k = 0; k < counts[j]; k++) {
                    arrays[index] = buckets[j][k];
                    index++;
                }
                counts[j] = 0; // 放空则计数归零
            }
            index = 0; // 一轮操作完毕，初始归零
        }
        return arrays;
    }

    // 执行
    public static void main(String[] args) {
        int[] input = new int[] { 163, 604, 196, 5, 561, 2, 73, 0, 18, 81, 495, 113, 220, 9, 284, 666 };
        System.out.println("样本初始样本数据：" + Arrays.toString(input));
        int[] output = RadixSort.sort(input);
        System.out.println("基数排序结果数据：" + Arrays.toString(output));
    }
}

算法延伸

  基数排序其实是桶排序原理的一种应用。桶排序，简单地说，就是把数据元素按照一定的规则分组，类似放在一个个的桶中，然后对每个桶里面的的数据再进行排序。
  这个桶里的排序，是递归这个排序本身也可以，也可以是之前提到的任何一种排序方式，总之，就是将大数据样本按规则顺序拆分，分批处理，然后再统入列。
  基数排序就是这样，按照数位从低到高排序并递归这个操作的。

算法分析

  选择排序算法的基本性能，归纳如下图：

其中，d代表待排最大元素位数，n代表元素个数。

1、 时间复杂度

  基数排序的时间复杂度是O(d×n)，其中d是排序元素个数，n是数字位数。
  留意这个d，如果待排最大元素位数比较小，基数排序的时间复杂度被认为接近于O(n)，即接近线性级别，性能比较优越；如果最大元素位数过长，甚至长过这个n，则它的时间复杂度则退化甚至差于O(n2)，此时，采用基数排序将不是最优方案。
  此外，基数排序的桶因素，因为桶数量k的选用是确定的较小常数，即一般不考虑为时间复杂度计算的主要因素。
  根据上边的程序分析说明等可了解到，基数排序的时间复杂度跟原数列是否有序，都需要从数位从低到高依次进行，跟其他因素没有太大关系，起决定作用的主要是d和n，故最好最坏，平均时间复杂度均是O(d×n)。

2、 空间复杂度

  跟据基数排序的特性，它的空间复杂度为O(n+k)，其中k为桶的数量，所有桶实际占用总容量足以分配n个元素即可。这里有个使用上容易产生误导的地方，当我们在程序层面开辟桶空间的时候，使用数组时，每个桶的长度肯定要考虑极端情况，桶长会被设置为整个待排元素的个数，会造成占用空间为k×n的假象；但如果从链表角度考虑，就完全不是这样子了。

3、稳定性

  在基数排序过程中，每次都是将当前位数上相同数值的元素统一“装桶”，并不需要交换位置。所以基数排序是稳定的算法。