Radixsort

算法输入：基数排序，输入一张有n个数的表L=｛a1,a2,…,an｝和k位数字

算法输出：按非降排列的L

算法思想：可以用数学归纳法证明，假定这些书的低k-1位数已经排好序，那么对第k位数完成排序之后，就可以完成所有的排序。

算法过程：首先根据最低位=1，把数分到表L1中；最低位=0的数，分到L0中；依次进行，直到这n个数字的最低位分配完毕。然后将这些表用顺序连接起来。进行次低位的排序，直到排序完成。

算法代码：

#include<stdio.h>
#include<malloc.h>

static int order = 1;
int main ()
{

    int N,i,length,j;
    int *a;
    printf("Please input the number of the array:");
    scanf("%d", &N);
    printf("Please input the length of the each_num:");
    scanf("%d", &length);
    a = (int* )malloc(N*sizeof(int));
    for(i=0; i<N; i++)
        scanf("%d",&a[i]);
    //因为子函数是一次排序，所以要多次
    for (j = 0; j < N; j++)
        radixsort(a, N, length);

    
    for (i = 0 ;i < N; i++)
        printf("%5d", a[i]);
}


// 一次排序的算法
void radixsort(int *A, int n, int k)
{
    //初始化,其中L大小是一个10*N大小的int型矩阵，假如有一位数字都是0，就全部放进去，所以就是N大小的。
    int **L,num[10];
    int each_k;
    int ini;
    int each_num;
    int i,j,l;

    L = (int**)malloc(10*sizeof(int*));
    for (ini = 0; ini < 10; ini++)
        L[ini] = (int*)malloc(n*sizeof(int));    //用的是中括号


    //取某一位的算法
//    for ( each_k = 0; each_k < k; ++each_k)
//    {
        //因为是新一次的排序，所以清空，num[i]用于记录当前循环放在L[Digit]的数目
        for ( ini = 0; ini < 10; ++ini)
            num[ini] = 0;

        for (each_num = 0; each_num < n; ++each_num)
        {
            //取出每一位数字，num[Digit]++是为了L[Digit]放入一个数字之后加一，为下一次放数字做准备。
            int Digit = (A[each_num]/order)%10;
            L[Digit][num[Digit]++] = A[each_num];
        }

//    }

    //将这次排序出来的结果连接成为一个新的数组

    int m = 0;
    for (j = 0; j < 10; ++j)
        for (l = 0; l < num[j]; ++l)
            A[m++] = L[j][l];

    order *= 10;

    for (ini = 0; ini < 10; ++ini)
        free(L[ini]);
    free(L);
}