1 #define MaxDigit 4 2 #define Radix 10 3 typedef struct Node *PtrToNode; 4 struct Node 5 { 6     int key; 7     PtrToNode Next;     8 }; 9 //定义桶头节点10 struct HeadNode11 {12     PtrToNode head;13     PtrToNode tail;14 };15 typedef struct HeadNode Bucket[Radix];16 /*17    X是所求的数，X是几位数 D就是几18 */19 int GetDigital(int X,int D)20 {21     int i,d;                 //d为返回值，是X在某位上的具体数22     for(i=1;i<=D;i++)23     {24         d=X%Radix;             //Radix =10;25         X/=Radix;             //Radix =10;26     }27     return d;28 }29 void LSDRadixSort(ElementType A[],int N)30 {31     Bucket B;32     int i ,D,Di;33     PtrToNode P,temp,list=NULL;34 35     /*初始化桶*/36     for(i=0;i<Radix;i++)37    38         B[i].head=B[i].tail=NULL;39     40    /*将数组逆序导入链表list*/41     for(i=0;i<N;i++)42     {43         temp=(PtrToNode)malloc(sizeof( struct Node));  //新建temp44         temp->key=A[i];     45         temp->Next=list;    // 第一次temp为list list为null46         list=temp;          //更新list 为temp47     }48     49     /*从最低位开始入桶*/50 51     for(D=1;D<=MaxDigit;D++)52     {    53         P=list;54         while(P)55         {56             Di=GetDigital(P->key,D);57             /*获取位数*/58             temp=P;59             P=P->Next;60             temp->Next=NULL;61             /*从list中摘除*/62             if(B[Di].head==NULL)63                 B[Di].head=B[Di].tail=temp;64             else65             {66                 B[Di].tail->Next=temp;67                 B[Di].tail=temp;68             }69         }70     71     /*收集*/72         list=NULL;73         for(Di=Radix-1;Di>=0;Di--)74         {75             if(B[Di].head)76             {77                 B[Di].tail->Next=list;78                 list=B[Di].head;79                 B[Di].head=B[Di].tail=NULL;//清空桶80             }81         }82     }83     /* 将list倒入A[]并释放空间 */84     for(i=0;i<N;i++)85     {86         temp=list;87         list=list->Next;88         A[i]=temp->key;89     //    printf(" i: %d  a: %d   ",i,A[i]);90         free(temp);91     }92 }