算法图示
元素分配到桶中
对桶中的元素进行排序
- 設置一個定量的陣列當作空桶子。
- 尋訪序列，並且把項目一個一個放到對應的桶子去。
- 對每個不是空的桶子進行排序。
- 從不是空的桶子裡把項目再放回原來的序列中。
如果桶足够小就变成了
计数排序, 计数排序是桶排序的一个特例
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
public static void sort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int max = 0;
int min = 0;
for (int i : arr) {
max = Math.max(max, i);
min = Math.min(min, i);
}
// 定义桶数量
int BUCKET_SIZE = 10;
int bucketCount = (max - min) / BUCKET_SIZE + 1;
// 定义桶
ArrayList<ArrayList<Integer>> buckets = new ArrayList<>();
for (int i = 0; i < bucketCount; i++) {
buckets.add(new ArrayList<Integer>());
}
// 初始化桶
for (int i : arr) {
int index = (i - min) / BUCKET_SIZE;
buckets.get(index).add(i);
}
// 对各个桶数据进行排序
for (ArrayList<Integer> bucket : buckets) {
// 这里的排序算法决定着桶的算法复杂度
Collections.sort(bucket);
}
// 桶拼接
int p = 0;
for (ArrayList<Integer> bucket : buckets) {
for (Integer integer : bucket) {
arr[p++] = integer;
}
}
}
时间复杂度
假设桶的数量是K, 数组长度是n
f(n) = n(计算最大/小) + k(定义桶) + n(初始化桶) + n^2(对桶进行排序,可以是任一排序算法,1~n^2) + n(桶拼接)
f(n)max = n(3+n)+k = O(n^2)
f(n)min = 3n+k = O(n)
桶的时间复杂度取决于对每个桶进行排序时的算法时间效率, 最好的情况下是桶中只有一个数据不需要排序 O(1), 最差的排序算法复杂度是O(n^2)
空间复杂度
链表结构存储桶, 假设有n个数,空间复杂度为O(n)
需注意, 本文用ArrayList有个初始大小10, 空间复杂度大于 O(n)
完整代码
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
class BucketSort {
public static void sort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int max = 0;
int min = 0;
for (int i : arr) {
max = Math.max(max, i);
min = Math.min(min, i);
}
// 定义桶数量
int BUCKET_SIZE = 10;
int bucketCount = (max - min) / BUCKET_SIZE + 1;
// 定义桶
ArrayList<ArrayList<Integer>> buckets = new ArrayList<>();
for (int i = 0; i < bucketCount; i++) {
buckets.add(new ArrayList<Integer>());
}
// 初始化桶
for (int i : arr) {
int index = (i - min) / BUCKET_SIZE;
buckets.get(index).add(i);
}
// 对各个桶数据进行排序
for (ArrayList<Integer> bucket : buckets) {
// 这里的排序算法决定着桶的算法复杂度
Collections.sort(bucket);
}
// 桶拼接
int p = 0;
for (ArrayList<Integer> bucket : buckets) {
for (Integer integer : bucket) {
arr[p++] = integer;
}
}
}
public static void main(String[] args) {
int[] array = {111, 52, 77, 98, 36, 12, 13, 48};
sort(array);
System.out.println(arrayToString(array));
}
private static String arrayToString(int[] array) {
StringBuilder builder = new StringBuilder();
for (int t : array) {
builder.append(t + " ");
}
return builder.toString();
}
}
