void   Distribute(RecordType1 r[],  int  i,  PVector head,  PVector tail)
/*  記錄數(shù)組r中記錄已按低位關(guān)鍵字key[i+1]，…，key[d]進(jìn)行過"低位優(yōu)先"排序。本算法按第i位關(guān)鍵字key[i]建立RADIX個(gè)隊(duì)列，同一個(gè)隊(duì)列中記錄的key[i]相同。head[j]和tail[j]分別指向各隊(duì)列中第一個(gè)和最后一個(gè)記錄（j=0，1，2，…，RADIX-1）。head[j]=0表示相應(yīng)隊(duì)列為空隊(duì)列*/ 
{
	int j;
	int p;
	for ( j=0 ; j<=RADIX-1 ; ++j)
		head[j]=0;                        /*  將RADIX個(gè)隊(duì)列初始化為空隊(duì)列 */ 
		p= r[0].next;                    /*  p指向鏈表中的第一個(gè)記錄 */ 
		while( p!=0 ) 
		{
			j=r[p].key[i];          /* 用記錄中第i位關(guān)鍵字求相應(yīng)隊(duì)列號(hào) */
			if  ( head[j]==0 ) 
				head[j]=p;    /* 將p所指向的結(jié)點(diǎn)加入第j個(gè)隊(duì)列中 */ 
			else
				r[tail[j]].next=p;
			tail[j]=p;
			p= r[p].next;
		}
} /*  Distribute  */ 

void  Collect(RecordType1  r[],  PVector head,  PVector tail)
/* 本算法從0到RADIX-1 掃描各隊(duì)列，將所有非空隊(duì)列首尾相接，重新鏈接成一個(gè)鏈表 */ 
{
	int j;
	int t;
	j=0;
	while (head[j]==0 )                 /* 找第一個(gè)非空隊(duì)列 */ 
		++j;
	r[0].next =head[j];
	t=tail[j];
	while ( j<RADIX-1 )                 /* 尋找并串接所有非空隊(duì)列 */
	{
		++j;
		while ( (j<RADIX-1 ) && (head[j]==0 ) )     /* 找下一個(gè)非空隊(duì)列 */ 
			++j;
		if ( head[j]!=0 )       /* 鏈接非空隊(duì)列 */ 
		{
			r[t].next =head[j];
			t=tail[j];
		} 
	}
	r[t].next =0;             /* t指向最后一個(gè)非空隊(duì)列中的最后一個(gè)結(jié)點(diǎn) */ 
}   /* Collect */ 

void  RadixSort (RecordType1 r[],int length )
/* length個(gè)記錄存放在數(shù)組r中，執(zhí)行本算法進(jìn)行基數(shù)排序后，鏈表中的記錄將按關(guān)鍵字從小到大的順序相鏈接。 */ 
{
	int i,n;
	int d;
	PVector head;
	PVector tail;
    n= length;
	for ( i=0 ; i<= n-1 ; ++i)  
		r[i].next=i+1;  /* 構(gòu)造靜態(tài)鏈表 */
	r[n].next =0;
	d= 3;
	for ( i =d-1; i>= 0; --i )       /* 從最低位子關(guān)鍵字開始，進(jìn)行d趟分配 和 收集*/
	{ 
		Distribute(r,i,head,tail);  /* 第i趟分配 */ 
		Collect(r,head,tail);       /* 第i趟收集 */ 
	}
}  /* RadixSort  */