1.桶排序的基本概念
计数排序假设输入是由一个小范围内的整数构成，而桶排序则假设输入由一个随机过程产生的，该过程将元素均匀而独立地分布在区间[0，1)上。当桶排序的输入符合均匀分布时，即可以线性期望时间运行。桶排序的思想是：把区间[0，1)划分成n个相同大小的子区间，成为桶（bucket），然后将n个输入数分布到各个桶中去，对各个桶中的数进行排序，然后按照次序把各个桶中的元素列出来即可。
数中给出了桶排序的伪代码，假设输入是一个含有n个元素的数组A，且每个元素满足0≤A[i]<1，另外需要一个辅助数组B[0....n-1]来存放链表（桶）。伪代码如下所示：
桶排序的伪代码.png
举个来说明桶排序的过程，假设现在有A={0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.68}，桶排序如下所示：
桶排序.png
2.java基本代码实现
/**
* @Project: 10.dataStructure
* @description: 桶排序
* @author: sunkang
* @create: 2018-08-22 11:42
* @ModificationHistory who when What
**/
public class BucketSort {
/**
*桶排序：
* * 桶排序假设输入元素均匀而独立的分布在区间[0，1）上；
* * 桶排序的核心思想是，将[0，1）分为n个大小相同的子区间，
* * 上一个区间里的元素都比下一个区间里的元素小，然后对
* * 所有区间里的元素排序，最后顺序输出所有区间里的元素，
* * 达到对所有元素排序的目的
*
* 一个桶表示一些区间范围的数
*
* @param A 将要排序的数组A
* @param range 表示桶的个数
*/
public void bucketSort(Double[] A,int range){
//1.创建一个数组B,表示桶的集合
List<Double>[] B = new LinkedList[range];
//2.填充B，使之每一个桶为空桶
for(int i=0;i<B.length;i++){
B[i] = new LinkedList<Double>();
}
//3.填充桶
for(int j=0;j<A.length;j++){
int index =(int) Math.floor(range * A[j]);
B[index].add(A[j]);
}
//4 各个桶排序，利用comparator进行排序，但是也可以用插入法进行排序
int count = 0;
for(int i= 0 ;i<B.length;i++){
List<Double> bucket = B[i];
bucket.sort(new Comparator<Double>() {
@Override
public int compare(Double o1, Double o2) {
return 01 >= 02 ? 1 : -1;
}
});
//5. 将排序好的桶的元素装入原数组A中
for( Double dou:bucket){
A[count++] = dou;
}
}
}
public static void display(Double[] arr){
for(Double a :arr){
System.out.print(a+",");
}
}
public static void main(String[] args) {
Double[] a = new Double[]{0.3, 0.6, 0.5,0.2,0.3,0.5,0.7,0.8,0.93,0.92,0.91};
new BucketSort().bucketSort(a,10);
display(a);
}
}
3.算法分析
我们注意到，在最坏的情况下，除了第八行以外，所有其他各行时间代价为O(n)，所以需要分析第八行中n次插入排序调用所花费的总时间
现在来分析调用插入排序的时间代价，假设ni是表示桶B[i]中元素个数的随机变量，因为插入的时间代价为平方阶的，所以桶排序的时间代价为：
桶排序的运行时间.png
最终求解为：
桶排序的期望运行时间为：θ(n)+n*O(2-1/n) = θ(n)。
