#include "base.h"

int ord(char c)
{//返回k的映射(個位整數)
   return c-'0';
}

void Distribute(SLCell r[],int i,ArrType &f,ArrType &e)
{//靜態鍵表L的r域中記錄已按(keys[0],...,keys[i-1])有序.本算法按
 //第i個關鍵字keys[i]建立RADIX個子表,使同一子表中記錄的keys[i]相同
 //f[0..RADIX-1]和e[0..RADIX-1]分別指向各子表中第一個和最后一個記錄
	int j,p;
	for(j=0;j<RADIX;j++)
		f[j]=0;						//各子表初始化為空表
	for(p=r[0].next;p;p=r[p].next)
	{
		j=ord(r[p].keys[i]);		//ord將記錄中第i個關鍵字映射到[0..RADIX-1]
		if(!f[j])
			f[j]=p;
		else
			r[e[j]].next=p;
		e[j]=p;						//將p所指的結點插入第j個子表中
	}
}

int succ(int j)
{//求后繼函數
	j=j+1;
	return j;
}

void Collect(SLCell r[],int i,ArrType &f,ArrType &e)
{//本算法按keys[i]自小至大地將f[0..RADIX-1]所指各子表依次鏈接成
 //一個鏈表,e[0..RADIX-1]為各子表的尾指針.
	int j,t;
	for(j=0;!f[j];j=succ(j))
		;								//找第一個非空子表，succ為求后繼函數
	r[0].next=f[j];
	t=e[j];								//r[0].next指向第一個非空子表中第一個結點
	while(j<RADIX-1)
	{
		for(j=succ(j);j<RADIX-1&&!f[j];j=succ(j))//找下一個非空子表
			;
		if(f[j])								//鏈接兩個非空子表
		{
			r[t].next=f[j];
			t=e[j];
		}
	}
	r[t].next=0;						//t指向最后一個非空子表中的最后一個結點
}

void RadixSort(SLList &SLL)
{//L是采用靜態鏈表表示的順序表.對L作基數排序,使得L成為按關鍵字
 //自小到大的有序靜態鏈表,L.r[0]為頭結點.
	int i;
	ArrType f,e;
	for(i=0;i<SLL.recnum;i++)
		SLL.r[i].next=i+1;
	SLL.r[SLL.recnum].next=0;			//將L改造為靜態鏈表
	for(i=0;i<SLL.keynum;i++)
	{//按最低位優先依次對各關鍵字進行分配和收集
		Distribute(SLL.r,i,f,e);			//第i趟分配
		Collect(SLL.r,i,f,e);				//第i趟收集
   }
 }