排序（5）：基数排序

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

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

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