前言

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

算法思想

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

算法步骤：

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

基数排序的方式可以采用 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}。

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

动态效果示意图：

代码实现

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1005;
int a[maxn];
/*思想：基数排序其实就是按位排序、实现时用分桶的方法
可以从低位到高位、也可以从高位到低位*/
void Radix_Sort(int n, int k) {
    vector<int> v[10];//10个位对应10个桶
    int radix = pow(10, k);
    int flag = 1;
    for (int i = 1; i <= n; i++) {
        if (a[i] >= radix) flag = 0;
        int w = (a[i] % radix) / (radix / 10);
        v[w].push_back(a[i]);
    }
    int cnt = 1;
    for (int i = 0; i <= 9; i++) {//从低到高枚举每个位
        for (int j = 0; j < v[i].size(); j++) {
            a[cnt++] = v[i][j];
        }
    }
    if (flag) return;
...

课后习题

【2013年真题】对给定的关键字序列 110，119，007，911，114，120，122 进行基数排序，则第 2 趟分配收集后得到的关键字序列是 
A.007，110，119，114，911，120，122         
B.007，110，119，114，911，122，120 
C.007，110，911，114，119，120，122         
D. 110，120，911，122，114，007，119 

参考答案：C
答案解析：基数排序的第 1 趟排序是按照个位数字来排序的，第 2 趟排序是按然十位数字的大小进行排序的，答案是 C 选项。