基数排序(RadixSort)

概念介绍

基于比较排序算法的下界(合并排序，堆排序，快速排序…等)是Ω(nLogn)，也就是说，他们不能做得比nLogn更好。
计数排序是一种线性时间排序算法，当元素在1到k的范围内时，以O(n+k)时间排序。

如果元素在1到n²的范围内呢?
这种情况不能使用计数排序，因为计数排序将花费O(n²)，这比基于比较的排序算法更差。
如何在线性时间内对这样一个数组进行排序呢？

基数排序(RadixSort)能解决此问题。
基数排序的思想是从最低有效位数到最高有效位数逐个数字排序。基数排序使用计数排序作为子程序进行排序。

基数排序属于桶排序，是一种稳定的排序。

基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机(Tabulation Machine)上的贡献。
它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

基数排序是否优于基于比较的排序算法如快速排序?
如果每个数字都有log₂ⁿ位，那么对于大范围的输入数字，基数的运行时间似乎比快速排序更好。
基数排序中隐藏的常数因子较高，而快速排序则更有效地使用硬件缓存。
此外，基数排序使用计数排序作为子程序，计数排序占用额外的空间来排序数字。
如针对手机号码排序

排序过程

以给数组 170, 45, 75, 90, 802, 24, 2, 66 排序为例，演示排序过程如下：

• 从低位开始将待排序的数按照这一位的值放到相应的编号为0~9的桶中（计数排序）
• 等到低位排完得到一个子序列，再将这个序列按照次低位的大小进入相应的桶中（计数排序)，
• 一直排到最高位为止，数组排序完成
  
  针对数组3，1，18，11，28，45，23，50，30的基数排序过程图解
  

排序方式

基数排序的两种方式：
高位优先：又称为最有效键(MSD),它的比较方向是由右至左；
低位优先：又称为最无效键(LSD),它的比较方向是由左至右；

复杂度

时间复杂度：
在基数排序中，因为没有比较操作，所以在复杂上，最好的情况与最坏的情况在时间上是一致的，均为 O(d * (n + r))。
其中，d 为位数，r 为基数，n 为原数组个数。

额外空间复杂度：O(n+m)
m 个桶与存放 n 个元素的空间

示例代码

public class RadixSortExample {
    public static void main(String[] args) {
        int arr1[] = { 170, 45, 75, 90, 802, 24, 2, 66,3,703,43,45 };
        radixSort1(arr1, arr1.length);
        print(arr1);

        int arr2[] = { 170, 45, 75, 90, 802, 24, 2, 66,3,703,43,45 };
        radixSort2(arr2,arr2.length);
        print(arr2);
    }

    // A function to do counting sort of arr[] according to the digit represented by exp.
    static void countSort(int arr[], int n, int exp, int radix) {
        int output[] = new int[n]; // output array
        int i;
        int count[] = new int[radix];
        Arrays.fill(count, 0);

        // Store count of occurrences in count[]
        for (i = 0; i < n; i++) {
            count[(arr[i] / exp) % radix]++;
        }

        // Change count[i] so that count[i] now contains actual position of this digit in output[]
        for (i = 1; i < radix; i++) {
            count[i] += count[i - 1];
        }
        // Build the output array
        for (i = n - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % radix] - 1] = arr[i];
            count[(arr[i] / exp) % radix]--;
        }

        // Copy the output array to arr[], so that arr[] now contains sorted numbers according to current digit
        for (i = 0; i < n; i++) {
            arr[i] = output[i];
        }
    }

    static void radixSort1(int arr[], int n) {
        int m = Arrays.stream(arr).max().getAsInt();
        int radix = 10;
        /**
         * Do counting sort for every digit.
         * Note that instead of passing digit number, exp is passed.
         * exp is 10^i where i is current digit number
         */
        for (int exp = 1; m / exp > 0; exp *= radix) {
            countSort(arr, n, exp,radix);
        }
    }

    public static void radixSort2(int[] number, int d){
        int k = 0;
        int n = 1;
        int m = 1; //控制键值排序依据在哪一位
        int[][]temp = new int[10][number.length]; //数组的第一维表示可能的余数0-9
        int[]order = new int[10]; //数组order[i]用来表示该位是i的数的个数
        while(m <= d) {
            for(int i = 0; i < number.length; i++) {
                int lsd = ((number[i] / n) % 10);
                temp[lsd][order[lsd]] = number[i];
                order[lsd]++;
            }
            for(int i = 0; i < 10; i++) {
                if(order[i] != 0) {
                    for (int j = 0; j < order[i]; j++) {
                        number[k] = temp[i][j];
                        k++;
                    }
                }
                order[i] = 0;
            }
            n *= 10;
            k = 0;
            m++;
        }
    }

    static void print(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}