桶排序（Bucket Sort）原理是将待排序数据分配到有限数量的桶里，再对每个桶里的数据进行排序，是一种线性时间排序算法。每一个桶（Bucket）代表一个区间范围，里面可以承载一个或多个元素。
- 第一步：创建桶，创建桶的数量等于待排序元素个数
- 第二步：确定各桶的区间跨度，因为最后一个桶只存放待排序数据中的最大值，因此
区间跨度 = (最大值 - 最小值) / (桶数量 - 1) - 第三步：遍历待排序数据，将每个数据对号放入各桶中
- 第四步：对各桶内元素分别排序；
- 第五步：遍历所有桶，按顺序输出所有元素即为最终排序好的元素。
复杂度分析
时间复杂度：O(n)
Java 代码实现
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
public class BucketSort {
public static void sort(double[] data) {
if (data == null || data.length == 0) {
return;
}
// 获取待排序数据中最大值和最小值，计算出差值
double max = data[0];
double min = data[0];
for (int i = 0; i < data.length; i++) {
if (data[i] > max) {
max = data[i];
} else if (data[i] < min) {
min = data[i];
}
}
double d = max - min;
// 初始化桶，桶数量等于待排序数据个数
int bucketNum = data.length;
ArrayList<LinkedList<Double>> bucketList = new ArrayList<>();
for (int i = 0; i < bucketNum; i++) {
bucketList.add(new LinkedList<>());
}
// 遍历待排序数据，将其放入对应桶中
for (int i = 0; i < data.length; i++) {
int num = (int) ((data[i] - min) * (bucketNum - 1) / d);
bucketList.get(num).add(data[i]);
}
// 每个桶执行内部排序
for (int i = 0; i < bucketList.size(); i++) {
Collections.sort(bucketList.get(i));
}
// 输出全部元素
int index = 0;
for (LinkedList<Double> list : bucketList) {
for (double element : list) {
data[index++] = element;
}
}
}
public static void main(String[] args) {
double[] data = {1.32, 1.68, 0.37, 1.16, 8.56, 3.25, 4.44, 6.54, 1.68, 2.66, 3.88, 5.49};
sort(data);
System.out.println(Arrays.toString(data));
}
}
运行结果
[0.37, 1.16, 1.32, 1.68, 1.68, 2.66, 3.25, 3.88, 4.44, 5.49, 6.54, 8.56]
说明：
(1) 查找待排序数据中的最大值8.56和最小值0.37，差值为8.19
(2) 确定桶数量：12（等于待排序数据个数）
(3) 确定各桶区间跨度：(8.56 - 0.37) / (12 - 1) = 0.75，各桶的区间范围分别为
[0.37, 1.06) [1.06, 1.81) [1.81, 2.56) [2.56, 3.31) [3.31, 4.06) [4.06, 4.81) [4.81, 5.56) [5.56, 6.31) [6.31, 7.06) [7.06, 7.81) [7.81, 8.56) [8.56, 8.56]
(4) 遍历待排序数据，将其放入对应桶中，以1.32为例，(1.32 - 0.37) * (12 - 1) / 8.19 = 1.27...，取整得1，将其放入第2个桶，其余入桶过程如下所示：
[] [1.32] [] [] [] [] [] [] [] [] [] []
[] [1.32, 1.68] [] [] [] [] [] [] [] [] [] []
[0.37] [1.32, 1.68] [] [] [] [] [] [] [] [] [] []
[0.37] [1.32, 1.68, 1.16] [] [] [] [] [] [] [] [] [] []
[0.37] [1.32, 1.68, 1.16] [] [] [] [] [] [] [] [] [] [8.56]
[0.37] [1.32, 1.68, 1.16] [] [3.25] [] [] [] [] [] [] [] [8.56]
[0.37] [1.32, 1.68, 1.16] [] [3.25] [] [4.44] [] [] [] [] [] [8.56]
[0.37] [1.32, 1.68, 1.16] [] [3.25] [] [4.44] [] [] [6.54] [] [] [8.56]
[0.37] [1.32, 1.68, 1.16, 1.68] [] [3.25] [] [4.44] [] [] [6.54] [] [] [8.56]
[0.37] [1.32, 1.68, 1.16, 1.68] [] [3.25, 2.66] [] [4.44] [] [] [6.54] [] [] [8.56]
[0.37] [1.32, 1.68, 1.16, 1.68] [] [3.25, 2.66] [3.88] [4.44] [] [] [6.54] [] [] [8.56]
[0.37] [1.32, 1.68, 1.16, 1.68] [] [3.25, 2.66] [3.88] [4.44] [] [] [6.54] [] [] [8.56]
[0.37] [1.32, 1.68, 1.16, 1.68] [] [3.25, 2.66] [3.88] [4.44] [5.49] [] [6.54] [] [] [8.56]
(5) 每个桶内执行排序
[0.37] [1.16, 1.32, 1.68, 1.68] [] [2.66, 3.25] [3.88] [4.44] [5.49] [] [6.54] [] [] [8.56]
(6) 遍历所有桶，按顺序输出
0.37, 1.16, 1.32, 1.68, 1.68, 2.66, 3.25, 3.88, 4.44, 5.49, 6.54, 8.56
网友评论