lradixsort.cpp

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

void RadixSort2(elemtype x[], int n, int m)
/*对记录x[0]--x[n-1]进行关键字为m位整型值的基数排序*/
/*桶结构为链式存储结构*/
{
   int i,j,k,l,Power;
   radixnode *p, *q;
   radixtype Head[10];

   Power=1;

   /*进行m次排序*/
   for(i=0;i<m;i++)
   {
      if(i==0) Power=1;
      else     Power=Power*10;

      /*初始化桶*/
      for(j=0;j<10;j++)
      {
	 Head[j].tub = j;
	 Head[j].link=NULL;
      }

      /*将记录按关键字第k位的大小放到相应桶的链中*/
      for(l=0;l<n;l++)
      {
	 k = x[l].key/Power - (x[l].key/(Power*10))*10;
	 q = (radixnode *)malloc(sizeof(radixnode));
	 q->key = x[l].key;
	 q->next = NULL;

	 p = Head[k].link;
	 if(p==NULL)
	 {
	    Head[k].link = q;
	 }
	 else
	 {
	    while(p->next != NULL) p=p->next;
	    p->next = q;
	 }
      }

      /**按照链的顺序收回各记录/
      l=0;
      for(j=0;j<10;j++)
      {
	 p = Head[j].link;
	 while(p != NULL)
	 {
	    x[l].key = p->key;
	    l++;
	    q = p->next;
	    free(p);
	    p=q;
	 }
      }
   }
}