桶排序

桶排序（bucket sort）假设输入均匀而独立的分布在区间[0,1)上，在满足假设时，可以以线性时间运行。

基本思想：把区间划分成n个相同大小的子区间，或称桶。然后将n个输入数分布到各个桶中，由于输入数在区间上均匀分布，一般不会出现一个桶中出现太多数的情况。然后对各个桶进行分别排序，最后将各桶中元素合并即可。

Java程序实现

（简便起见，程序中链表和排序部分使用Java标准库）

[code lang=”java”]import java.util.LinkedList; import java.util.Collections;

public class BucketSort{ @SuppressWarnings("unchecked") public static Double[] sort(double[] A){ int n = A.length; LinkedList<Double>[] B = (LinkedList<Double>[])new LinkedList[n]; for(int i = 0; i < n; i++){ int index = (int)Math.floor(A[i] * n); LinkedList<Double> list = B[index]; if(list == null){ list = new LinkedList<Double>(); B[index] = list; } list.add(Double.valueOf(A[i])); } for(int i = 0; i < n; i++){ LinkedList<Double> list = B[i]; if(list != null){ Collections.sort(list); } } LinkedList<Double> result = new LinkedList<Double>(); for(int i = 0; i < n; i++){ if(B[i] != null){ result.addAll(B[i]); } } Double[] C = (Double[]) result.toArray(new Double[n]); return C; }

public static void main(String[] args){
	double[] array = {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68};
	for(double i : array){
		System.out.print(i + ",");
	}
	System.out.print("\n");
	Double[] result = sort(array);
	for(double i : result){
		System.out.print(i + ",");
	}
}

} [/code]

算法复杂度

输入符合均匀分布时，桶排序的期望运行时间为\(\Theta(n)\)。当输入不满足均匀分布，如果输入满足：各个桶尺寸的平方和与总的元素数呈线性关系，桶排序仍以线性时间运行。