MENU

排序(5):基数排序

June 7, 2018 • 技术

系列文章目录

排序(1):直接插入排序,二分查找插入排序,希尔排序
排序(2):快速排序
排序(3):堆排序
排序(4):归并排序
排序(5):基数排序
排序(6):总结

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

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

基数排序的方式可以采用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)$时间的比较排序是原址排序。因此,当主存的容量比较宝贵时,我们可能会倾向于像快速排序这样的原址排序算法。

Archives QR Code Tip
QR Code for this page
Tipping QR Code