Java
public class BucketSort {
public static void main(String[] args) {
double array[] = { 0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.26, 0.12,
0.23, 0.68 };
bucketSort(array);
System.out.println(Arrays.toString(array));
}
public static void bucketSort(double array[]) {
int length = array.length;
ArrayList arrList[] = new ArrayList[length];
for (int i = 0; i < length; i++) {
//0.7到0.79放在第8個(gè)桶里,編號(hào)7吨枉；第一個(gè)桶放0到0.09
int temp = (int) Math.floor(10 * array[i]);
if (null == arrList[temp])
arrList[temp] = new ArrayList();
arrList[temp].add(array[i]);
}
// 對(duì)每個(gè)桶中的數(shù)進(jìn)行插入排序
for (int i = 0; i < length; i++) {
if (null != arrList[i]) {
Collections.sort(arrList[i]);
}
}
int count = 0;
for (int i = 0; i < length; i++) {
if (null != arrList[i]) {
Iterator iter = arrList[i].iterator();
while (iter.hasNext()) {
Double d = (Double) iter.next();
array[count] = d;
count++;
}
}
}
}
}
最壞情況運(yùn)行時(shí)間：
當(dāng)分布不均勻時(shí)揍堰，全部元素都分到一個(gè)桶中，則O(n^2)诗轻；也可以將插入排序換成堆排序钳宪、快速排序等，這樣最壞情況就是O(nlgn)扳炬。
最好情況運(yùn)行時(shí)間：
O(n)
