这是什么

基数排序有时也称为卡式排序（card sort）。因为直到现代计算机出现之前，它一直用于对老式穿孔卡的排序。

如果我们有N个整数，范围是1到M（或从0到M-1），我们可以利用这个信息得到一种快速的排序叫做桶式排序（bucket sort）。我们先预设一个数组，给个名字叫Count，大小为M，并初始化为零。于是，Count有M个单元，开始时他们都是空的，当A[i]被读入时，Count[A[i]增1。在所有的输入被读进以后，扫描数组Count，打印输出排好序的表。

直白点说

这里的意思就是说，首先M的范围是包含N的，假设你有一组数组{3,2,1,7,6,4,4}，假设我们有10个桶，分别是1号桶，2号桶...，...，10号桶，都是空的，我们遍历这个数组，比如第一个是3，那么我就往3号桶里放一个石子，以此类推，我们最后会有：

1号桶 - 1个石子2号桶 - 1个石子3号桶 - 1个石子4号桶 - 2个石子5号桶 - 空6号桶 - 1个石子7号桶 - 1个石子8号桶 - 空9号桶 - 空10号桶 - 空

所以当我们从1号桶开始数石子时，从1数到10，有一个石子我们就把当前桶号几下来，于是我们就会有：

1，2，3，4，4，6，7

有没有发现通过这种方式我们已经把原数组给排好序了。

一些例子

基数排序是这种方法的推广。下面举例说明一下。

设我们有10个数，范围在0到999之间，我们将其排序。一般来说，这是0到N^p-1间的N个数，p是某个常数。显然，我们不能使用桶式排序，那样桶就太多了（为了10个数的排序，我们要准备1000个桶，这里N=10, p = 3）。我们的策略是使用多趟桶式排序。这里我们使用最低有效位进行排序。

这里拿10个数的桶式排序进行举例。本例的输入是64, 8, 216, 512, 27, 729, 0, 1, 343, 125。

第一步我们按照最低优先位进行排序，也就是按个位数的大小进行排序，得到如下结果。

得到排序的结果为0，1，512，343，64，125，216，27，8，729

第二步我们按次最低有效位进行排序，也就是按十位数的大小进行排序。

得到排序的结果为0，1， 8，512，216，125，27，729，343，64。

最后一趟我们按最高位进行排序，也就是百位数。

得到排序的结果为0，1，8，27，64，125，216，343，512，729。

可以发现按照上述算法的我们的空间复杂度是N^2。

下面是代码实现：

#include <vector>#include <list>#include <iostream>#include <cmath>using std::vector;using std::list;using std::cout;using std::endl;int getNum(int n){    int i = 0;    while(n){        n = n / 10;        i++;    }    return i;   }int getLoopTimes(const vector<int> &array){    int ret = 0;    for(const auto &num : array){        int i = getNum(num);        if(i > ret){            ret = i;        }    }    return ret;}int getIndex(int num, int i){    if(i == 0){        return num % 10;    }    else{        return (int)(num / pow(10, i)) % 10;    }}void baseSort(const vector<int> &array){    int loopTimes = getLoopTimes(array); //循环次数也就是最高位数（base 10）    cout <<"循环次数：" << loopTimes << endl;    list<int> baseList;        //init baseList    for(const auto &num :  array){        baseList.emplace_back(num);    }        for(int i = 0; i < loopTimes; ++i){        list<int> listArray[10];        for(const auto &num : baseList){            const int index = getIndex(num, i);            cout << "index:" << index << endl;            listArray[index].emplace_back(num);        }        baseList.clear();        for(int i = 0; i < 10; ++i){            for(const auto &num : listArray[i]){                baseList.emplace_back(num);            }        }        for(const auto &num: baseList){            cout << num << " ";        }        cout << endl;    }}int main(){    vector<int> test = {64, 8, 216, 512, 27, 729, 0, 1, 343, 125};    baseSort(test);    return 0;}

测试结果如下，与文字描述一致：