radixsort2.cpp

数据结构c++-书的一些源代码

#define MAXNUM 100          /*桶中元素的最大个数*/

typedef int keytype;
typedef struct
{
   keytype key;
} elemtype;

void RadixSort1(elemtype x[], int n, int m);

main()
{
   elemtype Test[10]={710,342,45,686,6,841,429,134,68,264};
   int n=10, m=3, i;

   RadixSort1(Test,n,m);

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

void RadixSort1(elemtype x[], int n, int m)
/*对记录x[0]--x[n-1]进行关键字为m位整型值的基数排序*/
/*桶结构为二维数组*/
{
   int i,j,k,Number,Power;
   int c[10];                /*对应桶的计数器*/
   elemtype d[10][MAXNUM];   /*二维数组结构的桶*/

   k=1;
   Power=1;
   while(k <= m)
   {
      if(k==1) Power=1;
      else Power=Power*10;

      /*将各桶清空*/
      for(i=0;i<10;i++) c[i]=-1;

      /*将各记录放到相应的桶中*/
      for(i=0;i<n;i++)
      {
	 j = x[i].key/Power - (x[i].key/(Power*10))*10;
	 c[j] = c[j]+1;
	 d[j][c[j]] = x[i];
      }

      /*从桶中往回收集*/
      Number=0;
      for(i=0;i<10;i++)
      {
	 if(c[i]!=-1)
	 {
	    for(j=0;j <= c[i];j++)
	    {
	       x[Number]=d[i][j];
	       Number++;
	    }
	 }
      }
      k++;
   }
}