🤪 基数排序

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

template<typename T>
void printVec(vector<T>&t) {
    for (T& i : t) {
        cout << i << " ";
    }
    cout << endl;
}

//求待排序序列最大元素位数
int Maxbit(vector<int>&vec) {
    int max = vec[0],bits=0;
    for (int i = 1; i < vec.size(); i++) {
        if (vec[i] > max) {
            max = vec[i];
        }
    }
    //计算位数
    while (max!=0) {
        bits++;
        max /= 10;
    }
    return bits;
}

//取num的第bit位的数字
int Bitnumber(int num,int bit) {
    int temp = 1;
    for (int i = 1; i < bit; i++) {
        temp *= 10;
    }
    return (num / temp) % 10;
}

void RadixSort(vector<int>&vec) {
    int max_bit = Maxbit(vec);
    //分配空间
    int** B = new int* [10];
    for (int i = 0; i < 10; i++) {
        B[i] = new int[vec.size() + 1];
    }
    //每个桶存放元素的个数
    for (int i = 0; i < 10; i++) {
        B[i][0] = 0;
    }
    for (int bit = 1; bit <= max_bit;bit++) {
        //分配
        for (int j = 0; j < vec.size();j++) {
            int num = Bitnumber(vec[j],bit);//取vec[j]第bit位上的数字
            int index = ++B[num][0];
            B[num][index] = vec[j];
        }
        //收集
        for (int i = 0, j = 0; i < 10; i++) {
            for (int k = 1; k <= B[i][0]; k++) {
                vec[j++] = B[i][k];
            }
            B[i][0] = 0;
        }
    }
    //释放空间
    for (int i = 0; i < 10; i++) {
        delete[] B[i];
    }
    delete B;
}


int main(int argc,char**argv) {
    vector<int>vec = { 67,45,23,1,4,6,87,34,13 };
    RadixSort(vec);
    printVec<int>(vec);
    return 0;
}

//1 4 6 13 23 34 45 67 87