//桶式排序類

#include "Sorter.h"

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

//桶式排序，Array[]為待排序數組，數組長度為n,所有記錄都位于區間[min,max)上
template <class Record>
void BucketSorter<Record>::Sort(Record Array[], int n,int min,int max) 
{ 
  int* count=new int[max-min];
  int i,j;
  //所有計數器初始都為0
  for (i=min;i<max;i++)
    count[i]=0;
  //開始統計計數
  for (j=0;j<n;j++)
  count[Array[j]]++;
  //按順序輸出有序序列
  for (i=min,j=0;i<max;i++)
    while (count[i]>0)
	{
     Array[j++] =i;
     count[i]--;
	}
}