//桶式排序類
#include "Sorter.h"

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

//桶式排序，Array[]為待排序數組，數組長度為n,所有記錄都位于區間[0,max)上
template <class Record>
void BucketSorter<Record>::Sort(Record Array[], int n,int max) 
{ 
  int* TempArray=new Record[n];	//臨時數組
  int* count=new int[max];	//小于或等于i的元素個數
  int i;

  for (i=0;i<n;i++)
  	TempArray[i]=Array[i];
  //所有計數器初始都為0
  for (i=0;i<max;i++)
  	count[i]=0;
  //統計每個取值出現的次數
  for (i=0;i<n;i++)
	count[Array[i]]++;
  //統計小于等于i的元素個數
  for (i=1;i<max;i++)
  	count[i]=count[i-1]+count [i];
  
  //按順序輸出有序序列
  for (i=n-1;i>0;i--)
     Array[--count[TempArray[i]]] = TempArray[i];
}