基数排序与前面所述的排序方法都不同,它不需要比较关键字的大小。

它是这样实现的:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

基数排序的方式可以采用 LSD(Least significant digital)或 MSD(Most significant digital),LSD 的排序方式由键值的最右边开始,而 MSD 则相反,由键值的最左边开始。

不妨通过一个具体的实例来展示一下基数排序是如何进行的。 设有一个初始序列为: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。

我们知道,任何一个阿拉伯数,它的各个位数上的基数都是以 0~9 来表示的,所以我们不妨把 0~9 视为 10 个桶。

我们先根据序列的个位数的数字来进行分类,将其分到指定的桶中。例如:R[0] = 50,个位数上是 0,将这个数存入编号为 0 的桶中。

分类后,我们在从各个桶中,将这些数按照从编号 0 到编号 9 的顺序依次将所有数取出来。这时,得到的序列就是个位数上呈递增趋势的序列。

按照个位数排序: {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。

接下来,可以对十位数、百位数也按照这种方法进行排序,最后就能得到排序完成的序列。

代码如下:

/* 求出数组中元素最大的位数 */
int MaxBit(int array[], int n)
{
    // 数组最大值 
    int max_data = array[0];
    for (int i = 1; i < n; i++)
    {
        if (array[i] > max_data)
            max_data = array[i];
    }

    // 数组最大值的位数
    int bits_num = 0;
    while (max_data)
    {
        bits_num++;
        max_data /= 10;
    }

    return bits_num;
}

/* 基数排序 */
void RadixSort(int array[], int n)
{
    int bits_num = MaxBit(array, n);
    int radix = 1;
    int * temp = new int[n];    // 临时数组
    int * count = new int[10];  // 保存各个桶中的个数

    for (int i = 1; i <= bits_num; i++)
    {
        // 计数器清 0
        for (int j = 0; j < 10; j++)
            count[j] = 0;

        // 统计各个桶中的个数
        for (int j = 0; j < n; j++)
        {
            int k = (array[j] / radix) % 10;
            count[k]++;
        }

        // 索引重分配
        for (int j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j];

        // 放入临时数组,从右往左扫描,保证排序稳定性
        for (int j = n - 1; j >= 0; j--)
        {
            int k = (array[j] / radix) % 10;
            temp[count[k] - 1] = array[j];
            count[k]--;
        }

        // 临时数组复制到 array[] 中
        for (int j = 0; j < n; j++)
            array[j] = temp[j];

        radix *= 10;
    }

    delete[] temp;
    delete[] count;
}

基数排序的时间复杂度是 $O(k⋅n)$,其中 $n$ 是排序元素个数,$k$ 是最大的数字位数。

那基数排序是否比基于比较的排序算法(如快速排序)更好呢?(以下摘自算法导论)

$O(k⋅n)$ 与 $O(nlogn)$ 这一结果看上去确实是基数排序更好一点。但是在这两个表达式中,隐藏在 $O$ 符号背后的常数项因子是不同的。在处理的 $n$ 个关键字时,尽管基数排序执行的循环轮数会比快速排序要少,但每一轮它所耗费的时间要长得多。哪一个排序算法更合适依赖于具体实现和底层硬件的特性(例如,快速排序通常可以比基数排序更有效地使用硬件的缓存),以及输入数据的特征。此外,利用计数排序作为中间稳定排序的基数排序不是原址排序,而很多 $O(nlogn)$ 时间的比较排序是原址排序。因此,当主存的容量比较宝贵时,我们可能会倾向于像快速排序这样的原址排序算法。

其它

文章开源在 Github - blog-articles,点击 Watch 即可订阅本博客。 若文章有错误,请在 Issues 中提出,我会及时回复,谢谢。

如果您觉得文章不错,或者在生活和工作中帮助到了您,不妨给个 Star,谢谢。

(文章完)

文章作者:刘毅 (Ethson Liu)
发布日期:2019-10-22
原文链接:https://ethsonliu.com/2019/10/radix-sort.html
版权声明:文章版权归本人所有,欢迎转载,但必须保留此段声明,且在文章页面明显位置给出原文链接,否则保留追究法律责任的权利。