#include<iostream>
using namespace std;
int arr[] = { 53, 3, 542, 7480, 14, 214 };
const int length = sizeof(arr) / sizeof(arr[0]);
int main()
{
    void radixSort(int arr[]);
    /*int arr[] = { 53, 3, 542, 7480, 14, 214 };
    int length = sizeof(arr) / sizeof(arr[0]);*/
    
    cout << "基数排序前： " << endl;
    for (int i = 0; i < length; i++) {
        cout << arr[i] << " ";
    }

    cout << endl << "基数排序后： " << endl;
    radixSort(arr);
    for (int i = 0; i < length; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    system("pause");
    return 0;

}
void radixSort(int arr[])
{
    //得到数组中最大的位数
    int max = arr[0];
    for (int i = 1; i < length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }

    //得到最大数是几位数
    int maxlength = 0;
    while (max != 0)
    {
        max /= 10;
        maxlength++;

    }

    //定义一个二维数组，表示十个桶，每个桶就是一个一维数组
    //说明：
    //1.二维数组包含10个一维数组
    //2.为了防止在放入数的时候，数据溢出，则每一个一维数组（桶），大小定为arr.length
    //3.基数排序时使用空间换时间的经典算法
    int bucket[10][length];
    for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < length; j++)
        {
            bucket[i][j] = 0;
        }
    }

    //为了记录每个桶中，实际存放了多少个数据，我们定义一个一维数组来记录各个桶的每次放入的数据的个数
    //例如：bucketElementCounts[0],记录的就是bucket[0]桶放入的数据个数
    int bucketElementCounts[10];
    //10个数的初始值都为0；每多一个元素，初始值+1
    for (int i = 0; i < 10; i++)
    {
        bucketElementCounts[i] = 0;
    }

    for (int i = 0, n = 1; i < maxlength; i++, n *= 10) {
        //针对每个元素的对应位进行排序处理，第一次是个位的，第二次是十位的，第三次是百位的...
        for (int j = 0; j < length; j++) {
            //取出每个元素的对应位的值
            int digitOfElement = arr[j] / n % 10;
            //放入到对应的桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++;
        }
        //按照这个桶的顺序（一维数组的下标依次取出数据，放入原来数组）
        int index = 0;
        //遍历每一桶，并将桶中的数据，放入原来数组
        for (int k = 0; k < 10; k++) {
            //如果桶中有数据，我们才放入到原数组
            if (bucketElementCounts[k] != 0) {
                //循环该桶，即第k个桶（即第k个一维数组），放入
                for (int l = 0; l < bucketElementCounts[k]; l++) {
                    //取出元素放入到arr
                    arr[index] = bucket[k][l];
                    index++;
                }
            }
            //每轮处理后，需要将每个bucketElementCounts[k]=0!!!!!!
            bucketElementCounts[k] = 0;
        }

    }

}