关于基数排序要记住
1.唯一不基于比较的内排序
2.唯一时间复杂度在线性级别的内排序
3.稳定
4.时间复杂度与初始状态无关
基数排序的思想：
先分配:从左到右拿起数据，放到不同的桶子里面
后收集:从左到右拿起桶子，先进先出取出数据
类别
排序方法
最好时间
最坏时间
平均时间
空间复杂度
稳定性
序列特征
适用于
基数排序
r+n
d(r+n)
d(r+n)
r
稳定
分配+收集
关键字有较小的取值范围
一共要d（每个元素都是d位数据）轮分配收集，分配的时间复杂度是n（n个数据）, 收集的时间复杂度是r（r个桶子，r进制），时间复杂度一共是d*(n+r), 需要r个队列来做桶子，所以空间复杂度是o(r)
比如：1000，2312，3332进行排序，因为是4位数，所以要d=4轮，因为是十进制，所以要r=10个桶，数据一共n=3个,此时的时间复杂度是4*（10+3），空间复杂度是10个队列的大小。
编程注意事项：
1.考试的时候对基数排序算法的要求很低，为了深刻了解原理我还是实现了一下，为了简化问题，只考虑两位数的排序，那么就要进行两轮的分配和收集
2.由于要通过余数去寻找桶子的序号，所以原始序列最好从0开始存数据，免去不必要的麻烦。
/*收集*/ void collect(vector<int> &a, vector<queue<int> > &tong) { int k = 0; for (int i = 0; i < 10; i++) { while (!tong[i].empty()) { a[k] = tong[i].front(); tong[i].pop(); k++; } } } void basicSort(vector<int> a) { vector<queue<int> > tong(10);//十个桶子 int temp; /*分配个位数*/ for (int i = 0; i < a.size(); i++) { temp = a[i] % 10; tong[temp].push(a[i]); } /*收集个位数*/ collect(a, tong); /*分配十位数*/ for (int i = 0; i < a.size(); i++) { temp = (a[i] % 100-a[i])/10; tong[temp].push(a[i]); } /*收集十位数*/ collect(a, tong); /*输出*/ for (int i = 0; i < a.size(); i++)cout << a[i] << " "; }
