基数排序的原理与实现

一、前言

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。

比较型排序：常见的快速排序，归并排序，冒泡排序……等等，都是基于比较的排序算法。
比较型排序算法时间复杂度下界为O(N*log2N) ，
而非比较型排序算法有：计数排序，桶排序，基数排序等；
其中，计数排序，桶排序的时间复杂度分别为O(n+m)和O(n)，线性的时间复杂度。

计数排序和桶排序这么快，为什么STL, JDK等没有采用呢？
因为适用场景比较窄。
要使用这两个算法，需满足如下条件：
1、排序项是数值：这个就很伤了，比如不能用来排序字符串了，更不要说各种复杂对象了；
2、范围比较小：如果数值范围比较大，需要的计数器或者桶就会很多，空间复杂度上无法承受。

比如阿里面试题有一道是给2万名员工按年龄排序，就可以用计数排序或桶排序了，
因为年龄是整数，而且范围小，比如用桶排序，顶多100个桶就够了。

而基数排序，正是解决计数排序和桶排序数值范围局限性的良方。

二、原理

基数排序是这样实现的：
将所有待比较数值统一为同样的数字长度，数字较短的数前面补零。

然后，从最低位开始，依次进行一次排序。
这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

以上是以10为“基数”的过程演示。
整个过程经过三轮排序，先个位，再十位，然后是百位； 三轮排序完成后，整个数列就有序了。
那这三轮排序都是怎么操作的呢？计数排序或桶排序都可以。
所以基数排序和计数排序、桶排序的关系是一种拓展的关系。
其背后时一种时间和空间的交换。
比如说这里如果用1000个桶，那么只用一轮排序就好了（这就退化到计数排序了）。
这里先不讨论是否划算（用10为基通常是不划算的）， 先分析思想原理。

如果说基数排序的核心奥义是“按位切割，分别比较”的话，那么
计数排序就是：先统计，后索引；
桶排序则是：先分配，后收集。
什么时候用计数排序，什么时候用基数排序?
我的理解是，数组用计数排序，链表则用桶排序（收集的时候执行各个桶的元素首位相接即可）。

下面是整个基数排序的过程（用上面的数据为例）：

第一轮：
0: 170, 90
1:
2: 802, 2
3:
4: 24
5: 45,75
6: 66
7:
8:
9:

第二轮:
0: 802, 2
1:
2: 24
3:
4: 45
5:
6: 66
7: 170, 75
8:
9: 90

第三轮:
0: 2, 24, 45, 66, 75, 90
1: 170
2:
3:
4:
5:
6:
7:
8: 802
9:

最终，顺序为： 2, 24, 45, 66, 75, 90,170, 802
值得一提的是，实现这个过程的一个必要条件是：计数排序和桶排序是稳定排序。

三、实现

C++版本

template <class T>
void countSort(T *src, T *des, int n, int shift) {
    // 初始化统计变量为0
    int cnt[256] = { 0 };

    // 获取元素的value，通过位移和掩码获取[shift,shift+8]的bit, 索引到对应的统计变量(cnt)
    // 统计散落到各cnt的元素的数量
    for (int i = 0; i < n; i++) {
        T value = src[i];
        cnt[(value >> shift) & 0xFF]++;
    }

    // 根据cnt统计的元素个数，计算每个一组元素的末端位置
    for (int i = 1; i < 256; i++) {
        cnt[i] += cnt[i - 1];
    }

    // 再次根据元素的value索引到对应的统计变量(cnt)
    // 结合上一步前面计算的位置，将各个元素放到对应的位置（另一个素组）
    for (int i = n - 1; i >= 0; i--) {
        T value = src[i];
        des[--cnt[(value >> shift) & 0xFF]] = src[i];
    }
}

template <class T>
void rsort(T *src, int n) {
    T* des = new T[n];
    int size = sizeof(T);

    // 以256为基，则需要每次取元素的8bit进行计数排序，从低位到高位
    // bit为一个字节，则元素大小有多少个字节就需要进行多少次计数排序
    for (int i = 0; i < size; i++) {
        if (i % 2 == 0)
            countSort(src, des, n, i << 3);
        else
            countSort(des, src, n, i << 3);
    }

    delete[] des;
}

以上是基于计数排序的基数排序（很拗口？）
实现要点：
1、以256为基，每次统计8bit ;
2、用了泛型，以增加通用性。

选择256为基不是因为程序员强迫症，而是因为以2的次方作为基的，提取“位”可以通过位移和“与”操作来实现。
<<1 相当于乘2， <<2 相当于乘4，以此类推；
>>1 相当于除2；
&1 相当于余2。
对计算机来说，乘法、除法、求余是很费时的，而加减法，位运算等只需一个时钟周期。
对于一些2的次方的乘除和求余，可以换成等价的位运算。

比如上面的实现中：
以256为基，假如对int操作，可分为[31,24]、[23,16]、[15,8] 、[7,0] 四个“位”分别排序，
比方说要获取[15,8]的bit, 只需 (value >> 8) & 0xFF 即可。
而如果以10为基，则需用到除法和求余（%10），效率不高。

最终，可对2字节，4字节，8字节的数值类型进行排序(浮点数也可以), 只要是正数就行。
为什么浮点数也可以呢？
参考百科 https://zh.wikipedia.org/wiki/IEEE_754 “指数偏移值”一节。

下面是测试代码：

int main() {
    int n;

    int a[] = { 1, 9,-3, -4, 20,-10 };
    n = sizeof(a) / 4;
    rsort(a, n);
    for (int i = 0; i < n; i++) {
        printf("%d  ", a[i]);
    }
    printf("\n");

    __int64 c[] = { 1, 9,-3, -4, 20,-10 };
    n = sizeof(c) / 8;
    rsort(c, n);
    for (int i = 0; i < n; i++) {
        printf("%lld  ", c[i]);
    }
    printf("\n");

    float b[] = { 1.5f, 3.12f, -101.0f, 1.7f, -2.171828f, -0.618f };
    n = sizeof(b) / 4;
    rsort((int*)b, n);
    for (int i = 0; i < n; i++) {
        printf("%f  ", b[i]);
    }
    printf("\n");

    double d[] = { 1.5, 3.12, -101, 1.7, -2.171828, -0.618 };
    n = sizeof(d) / 8;
    rsort((__int64*)d, n);
    for (int i = 0; i < n; i++) {
        printf("%lf  ", d[i]);
    }
    printf("\n");

    return 0;
}

前面排序的实现中是没有对负数进行处理的，测试用例中强行加入一些负数，以便观察。

1、对正数的排序是没有问题的，无论是整数还是浮点数，4字节还是8字节；
2、整数的负数会呈降序，浮点数则仍更是升序；
3、负数会排在正数的后面。

基于第二和第三点， 再改进一下，兼容对负数的排序也是可以实现的。

不过，以上实现是对基本类型的排序，实际使用中，通常是对对象进行排序；
字符串这种就没法办了，基数排序只能解决数值范围的问题，
如果比较项不是数值，那也是鞭长莫及，这就是“非比较型排序”的硬伤。

但如果是根据对象的某个数值属性进行排序，那基数排序也是可以排上用场的。

Java版本

public class RadixSort {
    // 基数的设定，通常以8bit为基，也可以11,12,16为基
    // 基数增大，需要做的计数排序次数可能会降低，但需要计数器也会变多
    private static final int BIT = 8;
    private static final int MASK = ~((0x80000000) >> (31 - BIT)); // 0xFF
    private static final int COUNT = 1 << BIT; // 256
    private static final int ROUND = (32 / BIT) + (32 % BIT == 0 ? 0 : 1); // 4

    // int提取器
    public interface IntGetter<T> {
        int value(T o);
    }

    // 计数排序参数
    private static class Params {
        int[] cnt = new int[COUNT];
        // 将所有元素进行"|"运算，得到"mask"
        // 可以用于判断某一轮计数排序是否需要计算
        int mask;
        // 负数的个数
        int minus;
        // 组数的引用
        Object[] src;
        Object[] des;

        void swapBuffer() {
            Object[] t = src;
            src = des;
            des = t;
        }
    }

    private static void bucketSort(int shift, Params params, IntGetter intGetter) {
        Object[] src = params.src;
        int n = src.length;
        int[] cnt = params.cnt;
        boolean isFistRound = shift == 0;

        if (!isFistRound) {
            // 判断这一轮是否需要排序等
            // 如果mask的[shift, shift+BIT]位都为0，说明所有元素在这一段都为0，
            // 则这一轮就不需要排序了，尤其是对于所有元素都比较小时，高位有可能都为0
            if (((params.mask >> shift) & MASK) == 0) {
                return;
            }
            // 清空计数器
            for (int i = 0; i < COUNT; i++) {
                cnt[i] = 0;
            }
        }

        // 获取元素的value，通过位移和掩码获取[shift,shift+8]的bit, 索引到对应的统计变量(cnt)
        // 统计散落到各cnt的元素的数量
        for (int i = 0; i < n; i++) {
            int value = intGetter.value(src[i]);
            if (isFistRound) {
                params.mask |= value;
                params.minus += (value >> 31) & 1;
            }
            cnt[(value >> shift) & MASK]++;
        }

        // 判断第一轮是否需要排序
        if (isFistRound && (params.mask & MASK) == 0) {
            return;
        }

        // 根据cnt统计的元素个数，计算每个一组元素的末端位置
        for (int i = 1; i < COUNT; i++) {
            cnt[i] += cnt[i - 1];
        }

        if (params.des == null) {
            params.des = new Object[n];
        }

        // 再次根据元素的value索引到对应的统计变量(cnt)
        // 结合上一步前面计算的位置，将各个元素放到对应的位置（另一个素组）
        for (int i = n - 1; i >= 0; i--) {
            int value = intGetter.value(src[i]);
            params.des[--cnt[(value >> shift) & MASK]] = src[i];
        }

        // 交换des和src, 这样src总是指向排好序的数组
        params.swapBuffer();
    }

    public static void sort(final Object[] a, IntGetter intGetter) {
        int n = a == null ? 0 : a.length;
        if (n <= 1) {
            return;
        }

        Params params = new Params();
        params.src = a;

        //  从低位到高位进行计数排序
        int shift = 0;
        bucketSort(0, params, intGetter);
        for (int i = 1; i < ROUND; i++) {
            shift += BIT;
            if (((params.mask >> shift) & MASK) != 0) {
                bucketSort(shift, params, intGetter);
            }
        }

        // 经历了几轮计数排序之后，负数会排在数组后段，例如
        // [0 1 10 50 -4 -3]
        // 这时候只需调换负的序列和正的序列即可
        if (params.minus > 0) {
            int positive = n - params.minus;
            System.arraycopy(params.src, 0, params.des, params.minus, positive);
            System.arraycopy(params.src, positive, params.des, 0, params.minus);
            params.swapBuffer();
        }

        // 计数排序和swap正负序列之后，排序好的元素有可能落在临时数组，
        // 这时候需要把元素拷贝回a数组
        if (params.src != a) {
            System.arraycopy(params.src, 0, a, 0, n);
        }
    }
}

加上注释，有120行左右，但是基本实现和前面的C++版本是一样的。
不同之处在于，只实现了int的版本，这也是语言特性所致：
C/C++相对Java更底层一些，可以直接强转指针然后把float当int来算；
这在Java中是做不到的，当然也可以在IntGetter中返回 Float.floatToRawIntBits(value), 但是效率就低了，不建议。
所以先实现一个Int 的版本吧。

相对于上面的版本，这个版本做了这些事情：

• 通过定义IntGetter接口（作用类似于Comparator），使之可以对对象排序（如果对象的排序项是int值的话）；
• 兼容了负数的处理；
• 增加了空位判断，比方说如果是对年龄排序，[31,8]位都将会是0，这时候只需要对[7,0]做一轮排序即可。
• 增加基的配置，如果需要排序的数量很多，范围很广，调大基数是比较划算的。

最后一点，具体是这样的，比如将BIT=16, 则基数为2^16，
需要计数器65536个，但是计数排序只用经历两轮（低16位和高16位）。
如果要排序的数量很多，比方说上千万，那么这65536个计数器就是值得的（少了两趟千万级的计数排序）；
但如果数据没那么多，那可能遍历这65536个计数器花费还更多一些。
所以这不仅仅是空间换时间这么简单，如果使用不当，空间浪费了，时间上也没赚到。

那是否可以做一个动态的？根据n的大小调整基数。
嗯，也是可以的，不过少不了一番测试和对比。
本文主要是将基数排序的一些思想和基本实现，旨在抛砖引玉，有兴趣的读者可以尝试一下。
（其实是作者比较懒-_-）

和JDK的Collections.sort()做了下对比测试，数据为32bit随机数, 时间单位为毫秒。
结果如下：

JDK的排序实现据说是TimSort, 时间复杂度O(N*log2N);
数量较少时TimSort更快，
在1000~100000时是基数排序快，
当数量到达一百万时基数排序就相对变慢了。

然后如果测试数据都&0xFFFF( 相当于short类型），那么即使到10^7的量级，还是基数排序快；
或者以2^16为基，n比较大的话也会比TimSort快。

四、总结

基数排序是一种非比较型排序算法，解决了计数排序和桶排序在数值范围方面的局限性。
而本文中给出的基数排序实现，可以说是众多实现中比较通用的版本了。
不过总体而言，比较型排序的通用性还是更好。
平时开发的话用平台提供的排序算法就好了，但如果刚好碰上合适的场景，可以考虑一下基数排序。

参考资料：
https://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F
https://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95
https://baike.baidu.com/item/IEEE%20754/3869922?fr=aladdin