基数排序的原理与实现

  1. 云栖社区>
  2. 博客>
  3. 正文

基数排序的原理与实现

长风呼啸 2019-03-12 21:51:05 浏览679
展开阅读全文

一、前言

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

比较型排序:常见的快速排序,归并排序,冒泡排序……等等,都是基于比较的排序算法。
比较型排序算法时间复杂度下界为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随机数, 时间单位为毫秒。
结果如下:

n TimSort (JDK) RadixSort
100 0.126 0.92
1000 0.872 0.421
10000 5.795 3.713
100000 51.851 35.461
1000000 390.283 612.348
10000000 4093.365 6312.220

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

网友评论

登录后评论
0/500
评论
长风呼啸
+ 关注