线性时间运行的排序算法

桶式排序

桶式排序不再是基于比较的了，它和基数排序同属于分配类的排序，这类排序的特点是事先要知道待排序列的一些特征。

桶式排序事先要知道待排序列在一个范围内，而且这个范围应该不是很大的。

比如知道待排序列在[0,M）内，那么可以分配M个桶，第I个桶记录I的出现情况，最后根据每个桶收到的位置信息把数据输出成有序的形式。

这里我们用两个临时性数组，一个用于记录位置信息，一个用于方便输出数据成有序方式，另外我们假设数据落在0到MAX,如果所给数据不是从0开始，你可以把每个数减去最小的数。

publicclassBucketSorter{

publicvoidsort(int[]keys,intfrom,intlen,intmax)

{

int[]temp=newint[len];

int[]count=newint[max];

for(inti=0;i<len;i++)

{

count[keys[from+i]]++;

}

//calculatepositioninfo

for(inti=1;i<max;i++)

{

count[i]=count[i]+count[i-1];//thismeanshowmanynumberwhichislessorequalsthani,thusitisalsoposition+1

}

System.arraycopy(keys,from,temp,0,len);

for(intk=len-1;k>=0;k--)//fromtheendingtobeginningcankeepthestability

{

keys[--count[temp[k]]]=temp[k];//position+1=count

}

}

/**

*@paramargs

*/

publicstaticvoidmain(String[]args){

int[]a={1,4,8,3,2,9,5,0,7,6,9,10,9,13,14,15,11,12,17,16};

BucketSortersorter=newBucketSorter();

sorter.sort(a,0,a.length,20);//actuallyis18,but20willalsowork

for(inti=0;i<a.length;i++)

{

System.out.print(a[i]+",");

}

}

}