基数排序（只能排整数）

一种非比较的排序算法，根据每一额为来进行排序。通常用于整数排序

基本思想：通过对所有元素进行若干次分配和收集操作来实现排序

（1）步骤

1.获取待排序元素的最大值，并确定其位数

2.分配：从所有元素最低位开始遍历，根据所选取的位数的值对每个元素进行分配，分配到对应的桶中。

3.收集：每个桶是一个队列，先进去的先出。

重复上述步骤，直到对所有位都进行了排序

（2）理解

为什么会排好序呢？

因为我们根据每一位分配到桶中时，桶是有序的，因此桶的分配是正序的，我们收集的时候从最前面的桶开始收集，因此小的在前大的在后，我们根据第二位进行

（3）算法分析

时间复杂度：O(d(n+r))，其中d是数字位数，n是待排序的数量，r是基数。

位数较少时效率高。

空间复杂度：取决于桶的数量和存储方式。

（4）优缺点

优点：由于不需要元素间的比较，在排序范围有限或者元素有特定的顺序时，可能比比较型排序算法更有效 可以更容易排序有固定宽度的数字序列，如：电话号码，身份证

缺点：需要额外的桶，可能需要消耗较多内存 不能处理复杂的数据类型或非整数类型

class Solution {
const int MAXN = 50005; // 多少个元素
const int MAXT = 7;     // 最多的位数
const int BASE = 10;    // 基数，也就是进制

void RadixSort(vector<int>& a, int n) {
    int PowOfBase[MAXT]; // 桶的集合
    PowOfBase[0] = 1;
    for (int i = 1; i < MAXT; i++) {
        PowOfBase[i] = PowOfBase[i - 1] * BASE;
    }
    int RadixBucket[BASE][MAXN]; // 为每个桶开辟空间
    int RadixBucketTop[BASE];    // 存储每个桶的元素个数

    // 因为有负数，所以对每个数加上偏移量，加上最大的数
    for (int i = 0; i < n; i++) {
        a[i] += PowOfBase[MAXT - 1];
    }

    int pos = 0; // 当前指针所指的位
    while (pos < MAXT) {
        // 先排个位数
        memset(RadixBucketTop, 0,
            sizeof(RadixBucketTop)); // 代表每个桶目前没有元素
        for (int i = 0; i < n; i++) {
            int rdx = a[i] / PowOfBase[pos] % BASE; // 每个数对应位置的数
            RadixBucket[rdx][RadixBucketTop[rdx]++] = a[i];
        }
        int top = 0;
        for (int i = 0; i < BASE; i++) { // 遍历每个桶
            for (int j = 0; j < RadixBucketTop[i];
                j++) { // 对桶里的元素按顺序取出
                a[top++] = RadixBucket[i][j];
            }
        }
        pos++; // 排下一位
    }
    for (int i = 0; i < n; i++) {
        a[i] -= PowOfBase[MAXT - 1];
    }
}
public:
    vector<int> sortArray(vector<int>& nums) {
        RadixSort(nums,nums.size());
        return nums;
    }
};