桶排序

Published: 09 Sep 2011 Category:

桶排序(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 + &quot;,&quot;);
	}
	System.out.print(&quot;\n&quot;);
	Double[] result = sort(array);
	for(double i : result){
		System.out.print(i + &quot;,&quot;);
	}
}

} [/code]

算法复杂度

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