//基于靜態鏈的基數排序

//靜態隊列類

class StaticQueue{  
public:
    int head;
    int tail;
};

//基于靜態鏈的基數排序類
template <class Record>
class LinkRadixSorter{
private:
	void Distribute(Record* Array,int first,int i,int d,int r, StaticQueue* queue);		//分配過程
	void Collect(Record* Array, int& first, int i, int d, int r, StaticQueue* queue);	//收集過程
public:
	int Sort(Record* Array,int n, int d, int r);										//返回排序后第一個記錄的下標
	void PrintArray(Record* A, int first);												//輸出序列
};

//靜態鏈實現的基數排序，n為數組長度，d為排序碼個數，r為基數
template <class Record>
int LinkRadixSorter<Record>::Sort(Record* Array, int n, int d, int r) 
{ 
	int first=0;					// first指向靜態鏈中第一個記錄
	StaticQueue *queue;
	queue = new StaticQueue[r];		//存放r個桶的靜態隊列
	for (int i=0; i<n; i++)				// 建鏈，初始為next域指向下一個記錄
		Array[i].next = i+1;
	Array[n-1].next = -1;   	//鏈尾next為空

	for (int j=0; j<d; j++)			//對第j個排序碼進行分配和收集，一共d趟
	{
		Distribute(Array, first, j, d, r, queue);
		Collect(Array, first, j, d, r, queue);
	}
	return first;
}

//分配過程,Array中存放待排序記錄，first為靜態鏈中的第一個記錄,i為第i個排序碼，d為排序碼個數，r為基數
template <class Record>
void LinkRadixSorter<Record>::Distribute(Record* Array,int first,int i,int d,int r, StaticQueue* queue)  
{
	for (int j=0; j<r; j++)			//初始化r個隊列
		queue[j].head=-1;     
	while (first != -1)				//對整個靜態鏈進行分配
	{   
		int k=Array[first].key;		//取第i位排序碼數字k
		for (int a=0;a<i;a++)
			k= k/r;
		k=k%r;
		// 把Array[first]分配到第k個子序列中
		if (queue[k].head == -1)	//如果子序列為空，Array[first]就是第一個記錄
			queue[k].head = first;    
		else 
			Array[queue[k].tail].next = first;  // 加到子序列的尾部
		queue[k].tail = first;			//first為子序列的尾部	
		first = Array[first].next;		//繼續分配下一個記錄 
	}
}
//收集過程,Array中存放待排序記錄，first為靜態鏈中的第一個記錄，i為第i個排序碼，d為排序碼個數，r為基數
template <class Record>
void LinkRadixSorter<Record>::Collect(Record* Array, int& first, int i, int d, int r, StaticQueue* queue) 
{
	int last, k=0;								//已收集到的最后一個記錄
	while (queue[k].head == -1) k++;				// 找到第一個非空隊列    
	first = queue[k].head;
	last = queue[k].tail;
	
	while (k<r-1)								//繼續收集下一個非空隊列
	{
		k++; 
		while (k<r-1 && queue[k].head==-1) k++;	//找到下一個非空隊列
		if (queue[k].head!= -1) 
		{
			Array[last].next = queue[k].head;		//將這個非空序列與上一個非空序列連接起來
			last = queue[k].tail;					//此時最后一個記錄為這個序列的尾部記錄
		}
	}
	Array[last].next = -1;						//收集完畢
}

//輸出序列中所有內容
template <class Record>
void LinkRadixSorter<Record>::PrintArray(Record* Array, int first) 
{	//first為靜態鏈Array中第一個記錄的下標

	int tmp;							//用來掃描整個鏈的指針
	tmp = first;
	while (tmp != -1) 
	{
		cout << Array[tmp].key <<" ";	//輸出記錄
		tmp = Array[tmp].next;			//繼續指向下一個記錄
	}
	cout << '\n';
}