基数排序

/*
1.百位不同的数肯定会在第三轮进行正确的划分
2.百位相同十位不同的数会在第二轮进行正确的划分
3.百位相同十位相同个位不同的数会在第一轮进行正确的划分
4.其实每一轮都是一个排序，只不过我们要忽略些东西,基数排序是通过排序实现排序
5.小的数先进桶，所以输出时采用先进先出
*/
/*测试程序 实现LEN以内的排序*/
#define LEN 1000
int bucket[10][LEN];
int radix(int a[], int n)
{
        int i, j, k, m;
        int num = 1;
        int index;
        //先放入桶中，再从桶中拿出

        for(k = 0; k < 3; k++)
        {
                //初始化桶

                for(i = 0; i < 10; i++)
                        bucket[i][0] = 0;
                //放入桶中

                for(i = 0; i < n; i++)
                {
                        index = a[i] / num;
                        index = index % 10;//取该轮是对应桶的下标

                        bucket[index][++bucket[index][0]] = a[i];//放入桶中

                }
                //从桶中拿出

                for(i = 0, j = 0; i < 10; i++)
                {
                        for(m = 1; m <= bucket[i][0]; m++)
                                a[j++] = bucket[i][m];
                }

                num *= 10;
        }
     
}
int main()
{
        int a[] = {13, 51, 20, 23, 72, 353, 359, 20, 720, 587, 57, 583};
        int len = sizeof(a) / sizeof(int);
        int i;

        radix(a, len);

        for(i = 0; i < len; i++)
                printf("%d ", a[i]);
        printf("\n");
}