//基數排序類
#include "Sorter.h"

template <class Record>
class RadixSorter:public Sorter<Record,Compare>
{
public:
	void Sort(Record Array[],int n,int min,int max);
};

//數組實現的基數排序，n為數組長度，d為排序碼個數，r為基數
template <class Record>
void RadixSorter<Record>::Sort(Record Array[], int n,int d, int r) 
{ 
	Record *TempArray =new Record[n];	//輔助排序的臨時數組
	int* count= new int[r];				//計數器，Count[i] 存儲了第i個桶中的記錄數
	int i,j,k;
	int Radix=1;							//用來取Array[j]的第i位排序碼
	for (i=1; i<=d; i++)				// 分別對第i個排序碼進行分配
	{
		for (j=0; j<r; j++)				// 初始計數器均為0
			count[j] = 0;    
		 for (j=0; j<n; j++)			// 統計每個桶中的記錄數
		 {
			k=(Array[j] /Radix)%r;		//取Array[j]的第i位排序碼
			count[k]++;					//相應計數器加1
		 }
    
		for (j=1; j<r; j++)				// 將TempArray中的位置依次分配給r個桶
			count[j] = count[j-1] + count[j];
		for (j=n-1; j>=0; j--)			// 將所有桶中的記錄依次收集到TempArray中 
		{
			k=(Array[j] /Radix)%r;		//取Array[j]的第i位排序碼
			count[k]--;					//從第k個桶中取出一個記錄，計數器減1
			TempArray[count[k]] = Array[j];
		}
		for (j=0; j<n; j++)				// 將臨時數組中的內容復制到Array中
			Array[j] = TempArray[j];         
		Radix*=r;
	}
}