#include <iostream>
using namespace std;
/**
 arr 排列的数组
 d 数据的位数 （1,10,100）
 n 数据的个数
 **/
void radixSort(int arr[],int d,int n){
    //当前位数
    int currentD = 1;
    //arr的索引
    int k = 0;
    //10个桶,记得初始化
    int countInBucket[10]  = {0};
    //存储每次桶排序后的结果
    int bucket[10][n];

    while (currentD<d) {
        for (int i=0; i<n; i++) {
            //用于比较的位上的数
            int j = (arr[i]/currentD)%10;
            bucket[j][countInBucket[j]] = arr[i];
            //桶内元素个数+1
            countInBucket[j]++;
        }
        for (int i=0; i<10; i++) {
                //桶内有元素
            if (countInBucket[i]!=0) {
                for (int j =0; j<countInBucket[i]; j++) {
                    arr[k] = bucket[i][j];
                    k++;
                }
            }
            countInBucket[i] = 0;
        }
        k = 0;
        currentD = currentD*10;
    }

}


int main(int argc, const char * argv[]) {
    int a[] = {12,3,1,4,2,5,4,8,5,4,3,9,4,0};
    radixSort(a, 100, 14);
    for (int i=0; i<14; i++) {
        cout<<a[i]<<" ";
    }
    cout<<endl;
    return 0;
}