基數排序

基數排序的C語言描述：

#include<stdio.h>

typedef struct

{

  int num;

  int next;

}slcell;         //靜态連結清單的結點類型

#define M 10

int f[M];

int e[M];

int head=0;

void distribute(slcell *a,int w)

  int i;

  int last;

  for(i=0;i<10;i++)

   f[i]=-1;

  for(i=head;i!=-1;i=a[i].next)

  {

    last=(a[i].num/w)%10;

    if(f[last]==-1)

 f[last]=i;

 else

 a[e[last]].next=i;

 e[last]=i;

  }  

}             

//某一次排序

void collect(slcell *a)

  int l = -1;

    for (i=0; i<10; i++)

        if (f[i] != -1)

            if (l == -1)

                head = f[i];

            else

                a[l].next = f[i];

                l = e[i];

        }

 a[l].next = -1;

}                  

//将排序好的數組恢複成靜态連結清單

void Output(slcell *a, int head)

    while (head != -1) {

        printf("%4d", a[head].num);

        head = a[head].next;

    }

    printf("\n");

}                       

//輸出靜态連結清單中的值

void main()

 int i,max,k=1;

 slcell a[M];

 printf("請依次輸入%d個整數\n",M);

 printf("請輸入第1個數:");

 scanf("%d",&a[0].num);

 a[0].next=1;

 max=a[0].num;

 for(i=1;i<M;i++)

 {

 printf("請輸入第%d個數:",i+1);

    scanf("%d",&a[i].num);

 a[i].next=i+1;

 if(max<a[i].num)

  max=a[i].num;

 }

    a[M-1].next=-1;

 for(i=1;i<max;i=i*10)

  distribute(a,i);

  collect(a);

  printf("第%d排序的結果是：\n",k);

  Output(a,head);