文字部分为转载：http://hxraid.iteye.com/blog/647759
对N个关键字进行桶排序的时间复杂度分为两个部分：
(1) 循环计算每个关键字的桶映射函数，这个时间复杂度是O(N)。
(2) 利用先进的比较排序算法对每个桶内的所有数据进行排序，其时间复杂度为
∑ O(Ni*logNi) 。其中Ni 为第i个桶的数据量。
很显然，第(2)部分是桶排序性能好坏的决定因素。尽量减少桶内数据的数量是提高效率的唯一办法(因为基于比较排序的最好平均时间复杂度只能达到O(N*logN)了)。因此，我们需要尽量做到下面两点：
(1) 映射函数f(k)能够将N个数据平均的分配到M个桶中，这样每个桶就有[N/M]个数据量。
(2) 尽量的增大桶的数量。极限情况下每个桶只能得到一个数据，这样就完全避开了桶内数据的“比较”排序操作。当然，做到这一点很不容易，数据量巨大的情况下，f(k)函数会使得桶集合的数量巨大，空间浪费严重。这就是一个时间代价和空间代价的权衡问题了。
对于N个待排数据，M个桶，平均每个桶[N/M]个数据的桶排序平均时间复杂度为：
O(N)+O(M*(N/M)log(N/M))=O(N+N(logN-logM))=O(N+NlogN-NlogM)
当N=M时，即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。
总结： 桶排序的平均时间复杂度为线性的O(N+C)，其中C=N*(logN-logM)。如果相对于同样的N，桶数量M越大，其效率越高，最好的时间复杂度达到O(N)。 当然桶排序的空间复杂度 为O(N+M)，如果输入数据非常庞大，而桶的数量也非常多，则空间代价无疑是昂贵的。此外，桶排序是稳定的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| package sort;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
//类名：Arrays_Bucket
//属性：
//方法：
class Arrays_Bucket{
private int[] arrays;
private int curNum;
public Arrays_Bucket(int max) { //建立一个max长度的空数组
super();
arrays = new int[max];
curNum = 0;
}
public void insert(int value){ //往空的数组里面增加元素
arrays[curNum] = value;
curNum++;
}
public void display(){ //显示数组
System.out.println(Arrays.toString(arrays));
}
public static final int ARRAY_SIZE = 10000; //数组中最大的数的值
public static final int BUCKET_SIZE=10; //桶的大小，桶的数量极限等于数组大小，就可以避免桶内的排序
public void BucketSort(){
ArrayList<ArrayList<Integer>> bucket=new ArrayList<ArrayList<Integer>>();
for(int i=0;i<BUCKET_SIZE;i++) //建立10个桶
{
bucket.add(new ArrayList<Integer>());
}
for(int i=0;i<arrays.length;i++) //按大小把数组分配到不同的桶中
{
int k=arrays[i]/(ARRAY_SIZE/BUCKET_SIZE);
// System.out.println("k="+k);
bucket.get(k).add(arrays[i]);
}
for(ArrayList<Integer> list:bucket) //对桶内的元素进行排序
Collections.sort(list);
for(ArrayList<Integer> list:bucket) //从小到大输出桶内的元素
System.out.println(list);
}
}
public class BucketSort {
public static void main(String[] args) {
// TODO 自动生成的方法存根
int maxSize = 5;
Arrays_Bucket arrays_demo = new Arrays_Bucket(maxSize);
arrays_demo.insert(580);
arrays_demo.insert(570);
arrays_demo.insert(560);
arrays_demo.insert(600);
arrays_demo.insert(1590);
arrays_demo.display();
arrays_demo.BucketSort();
//arrays_demo.display();
}
}
|
