#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <conio.h>
#include <iostream.h>
#include <string.h>
#include <math.h>
//#include <algorithm>
//using namespace std;
#define MAX 10000
int r[MAX];
#define RADIX 10
#define D 5


typedef struct node //定義每一個數為一個結點
{
int key[5]; //該數字為五位數字
int next;
}NODE;

void convert(int num,int converted[])//將每個數字的每個數位（從高位到低位）存儲在key[0]～key[5]中
{
int i,temp;
temp=num;
for(i=0;i<D;i++)
{
converted[i]=temp/(int(pow(10,D-i-1)));

temp=temp-converted[i]*(int(pow(10,D-i-1)));

}
}

void RadixSort(NODE r[],int d,int radix,int n) //基數排序
{ 
int h[RADIX],t[RADIX];
int p,i,j,k;


for(i=1;i<n;i++) r[i].next=i+1; //將n個數字用指針連成一個鏈
r[n].next=0; r[0].next=1;

for(j=d-1;j>=0;j--) //用j控制排序的次數（有幾位數字就需要幾次排序）
{ 
for(i=0;i<radix;i++) { h[i]=t[i]=0; }
p=r[0].next;
while(p)
{
i=r[p].key[j];
if(h[i]) 
{ r[t[i]].next=p;
t[i]=p;
p=r[p].next;
}
else
{
h[i]=t[i]=p;
p=r[p].next;
}
}
i=0;
while(!h[i]) ++i;
r[0].next=h[i];k=i+1;
while(k<radix)
{
if(h[k]) { r[t[i]].next=h[k];i=k;}
k++;
}
r[t[i]].next=0;
}

}

void main()
{
clock_t start=clock();/*程序開始運行的時間*/
int i,j,num ;
NODE List[MAX];


printf("Please input the number of the numbers: ");
scanf("%d",&num);

//srand((unsigned int)time(NULL));//隨時間的不同產生不同的隨機數
for(i=0;i<num;i++)
{
r[i]=rand()%num+1;
}
printf("The %d nums is produced automatically:\n",num);
for(i=0;i<num;i++)
{ printf("%10d",r[i]); }


for(i=0;i<num;i++)
{
convert(r[i],List[i+1].key );//將每個數字的每個數位（從高位到低位）存儲在key[0]～key[4]中
}

RadixSort(List,D,RADIX,num); //基數排序
i=List[0].next;
//getch();

printf("\nAfter sorting:\n");
while(i)
{ for(j=0;j<D;j++) printf("%d",List[i].key[j] ); //一個for循環只輸出一個五位數字
printf("->");
i=List[i].next;//當i=List[num].next=0時,while循環結束
}

clock_t end=clock(); /*程序結束運行的時間*/
cout<<"\n"<<"整個程序運行的時間為:";
cout<<(end-start)<<"毫秒\n"; 
}