基排序

基于桶排序来实现。通过键值的部分信息，将要排序的元素分配至某些“桶”中，以此达到排序的作用。基数排序的方式可以采用LSD或MSD，LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始
时间复杂度：O(p(n+b))
其中：分配为O(n)、收集为O(b)、p为收集分配趟数
空间复杂度：O(n+b)

// 假设元素最多有MaxDigit个关键字，基数全是同样的Radix
#define MaxDigit 4
#define Radix 10

// 默认次位D=1, 主位D<=MaxDigit
int GetDigit(int X, int D) {
    int d;
    for (int i = 1; i <= D; i++) {
        d = X % Radix;
        X /= Radix;
    }
    return d;
}

// 基数排序 - 次位优先
void LSDRadixSort(int array[], int size) {
    vector<list<int>> arr(Radix);
    // 将原始序列存入链表list
    list<int> list;
    for (int i = 0; i < size; i++) {
        list.push_back(array[i]);
    }
    // 开始排序
    for (int D = 1; D <= MaxDigit; D++) {
        // 分配
        for (auto& i : list) {
            int Di = GetDigit(i, D);
            arr[Di].push_back(i);
        }
        // 收集
        list.clear();
        for (auto& l : arr) {
            list.insert(list.end(), l.begin(), l.end());
            l.clear();
        }
    }
    // 将list倒入array[]
    for (int i = 0; i < size; i++) {
        array[i] = *list.begin();
        list.pop_front();
    }
}

// 核心递归函数：对array[L]...array[R]的第D位数进行排序
void MSD(int array[], int L, int R, int D) {
    if (D == 0) {
        return;
    }
    vector<list<int>> arr(Radix);
    // 将原始序列存入链表list
    list<int> list;
    for (int i = L; i <= R; i++) {
        list.push_back(array[i]);
    }
    // 分配
    for (auto& i : list) {
        int Di = GetDigit(i, D);
        arr[Di].push_back(i);
    }
    // 收集
    int left = L;
    int right = L;
    for (auto& l : arr) {
        for (auto& i : l) {
            array[right++] = i;
        }
        // 递归对该桶数据排序，位数减1
        MSD(array, left, right - 1, D - 1);
        left = right;
    }
}

// 基数排序 - 主位优先
void MSDRadixSort(int array[], int size) {
    MSD(array, 0, size - 1, MaxDigit);
}