基数排序

• “基数排序”是数列排序的算法之一。
• 属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）。
• 基数，是同一类若干数据的集合，比如基数为个位数，那么个位数就是所有个位的数字的集合，通俗来说，你可以简单的理解为位数。
• “基数排序”通常有两种排序思路，一种是从低位到高位，称之为LSD（Least significant digital），相对的，另一种是从高位到低位，称之为 MSD (Most significant digital）。虽然看起来都是通过基数来进行排序的，但从低到高和从高到低的方法却是完全不同的，本文只展示比较简单的：LSD。

一、算法思路

首先我们要明白，在复数范围内，所有的数都是由0-9组成的，比较0-9就是我们在求学经历上，去比较两个数大小的最直观的判断。

在这里，我们将这十个基本的数字称之为“键值”。

假设我们有如图数列。

当基数为1时，即基数为个位数时，我们可以将数列中所有元素的个位数找出。

然后通过对比键值，将基数所代表的原数据，依次填入到键值组中。

最后，我们按键值从0到9的，将键值组中的数再次排列成一个新的数列。

如果我们利用同位素标记法标记出这次操作里进行关注的数字，可以发现我们这次操作中只对基数为1的数进行了排序。

• 其实通过这一次的操作，并没有完成排序。但如果继续观察，不难发现，我们已经对基数为1对数进行了部分排序，也就是说，我们可以保证：如果十位数相同，那么个位数必然十有序的。

然后，我们进行同样的操作。将基数设置为10.即十位数，将数列中所有元素的十位数找出。

同样的，通过对比键值，将基数所代表的原数据，依次填入到键值组中。

我们按键值从0到9的，将键值组中的数再次排列成一个新的数列。

利用同位素标记法标记出这次操作里进行关注的数字，可以发现我们这次操作中只对基数为10的数进行了排序。

• 我们不难发现，数列中所有的数字，都已经进行了排序，从而整个数列完成了排序。

整个过程如下：

二、代码清单及测试结果

#include <iostream>
#include <math.h>
#include <ctime>
template <class T>
/*
 * 获取数组长度
 */
int getSizeOfArray(T& bs){
    return sizeof(bs)/sizeof(bs[0]);
}

/*
 * 获取数组中最大的数
 */
int getMaximumOfArray(int *rs,int size){
    int max = rs[0];
    for(int i=size-1;i>0;i--){
        if(max<rs[i]){
            max = rs[i];
        }
    }
    return max;
}

/*
 * 获取一个数的位数
 */
int getByteOfNumber(int number){
    int byte = 0;
    int consult = -1;//商
    while(consult!=0){
        consult = number/10;
        byte++;
        number = consult;
    }
    return byte;
}

/*
 * 基数排序，利用LSD对数列进行排序
 */
void radixSort(int *rs,int size){
    int radix = 1;//基数初始化
    int max = getMaximumOfArray(rs,size);//最大值
    int byte = getByteOfNumber(max);//最大值位数
    int bucket[size];//初始化桶子（index代表键值）
    int count[10];//初始化桶子元素计数器(记录键值行所含的元素个数)
    int remainder[size];//初始化余数数列
    int startIndex[10];//初始化键值的起始位数列

    for(int i=1;i<=byte;i++){
        //桶子元素计数器和键值的起始位数列每次使用前进行归位操作
        for(int j=0;j<10;j++){
            count[j] = 0;
            startIndex[j] = -1;
        }
        //余数数列每次使用前进行清零操作
        for(int j=0;j<size;j++){
            remainder[j] = 0;
        }

        //计算键值行个数
        for(int j=0;j<size;j++){
            int re = (rs[j]/radix)%10;
            remainder[j] = re;
            count[re]++;
        }
        //利用桶子元素计数器计算各键值的起始位
        int sum = 0;
        for(int j=0;j<10;j++){
            if(count[j]!=0){
                startIndex[j] = sum;
                sum += count[j];
            }
        }
        //进桶
        for(int j=0;j<size;j++){
            bucket[startIndex[remainder[j]]] = rs[j];
            startIndex[remainder[j]]++;
        }
        //出桶
        for(int j=0;j<size;j++){
            rs[j] = bucket[j];
        }
        //基数扩大
        radix = radix * 10;
    }
}


int main() {
    using namespace std;

    int rs[] = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81};
    int size = getSizeOfArray(rs);

//    clock_t startTime,endTime;

    cout<< "原数列:";

    for(int i = 0;i<size;i++)
    {
        cout<< rs[i] << " ";
    }

    cout<< "\n" << "基数排序后:";

//    startTime = clock();
    radixSort(rs,size);
//    endTime = clock();

    for(int i = 0;i<size;i++)
    {
        cout<< rs[i] << " ";
    }

//    cout << "\n"<<"The run time is: " <<(double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;

    return 0;
}

三、算法分析

“时间效率 ：设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集。 空间效率：需要2*radix个指向队列的辅助空间，以及用于静态链表的n个指针。”

上述分析来自引用：

https://www.cs.auckland.ac.nz/software/AlgAnim/radixsort.html