排序算法 --- 桶排序
一、排序思想
之前将的计数排序，有些局限性，比如数列最大值和最小值差距不能太大，而且只能排整数。桶排序就对这些局限性做了弥补。桶排序的思想就是每个桶代表一个区间范围，里面可以装若干个元素。然后对这些桶内部进行排序，最后遍历这些桶，那么数列就是有序的了。
欢迎大家关注我的公众号 javawebkf，目前正在慢慢地将简书文章搬到公众号，以后简书和公众号文章将同步更新，且简书上的付费文章在公众号上将免费。
1. 案例：
假如现在有如下数列：
4.5, 0.84, 3.25, 2.18, 0.5- 首先创建与元素个数相同的桶，这里就创建5个桶；
- 最后一个桶让它只包含最大元素，即只包含4.5；
- 最大数是4.5，最小是0.5，间距是4，除去最后一个桶还有4个桶，所以每个桶间距是1，如下图：
桶排序
- 然后开始遍历原始数列，把元素放入对应的桶中，如下：
桶排序
- 对每个桶内部的元素进行排序，如下：
桶排序
- 最后遍历所有的桶，输出的元素就是有序的了。
桶排序的缺点：如果数据分布不均衡，比如最大值1000，最小值0.5，剩余元素都是零点几的，也就是说最后一个桶放最大元素，其他元素都在第一个桶，这样性能就会下降，并且创建了很多空桶，浪费空间。
二、代码实现
public static void sort(double[] arr){
if (arr == null || arr.length == 1){
return;
}
int arrNum = arr.length; // 元素个数
// 拿到最大数和最小数，用来确定间距
double max = arr[0];
double min = arr[1];
for (int i = 0; i < arrNum; i++) {
max = arr[i] > max ? arr[i] : max;
min = arr[i] < min ? arr[i] : min;
}
double distance = max - min;
// 创建 arrNum 个桶，桶用linkedList表示，因为linkedList是可重复的，待排数列可能有相同的元素
List<LinkedList<Double>> buckets = new ArrayList<>();
for (int i = 0; i < arrNum; i++) {
buckets.add(new LinkedList<>());
}
// 遍历原始数组，将每个元素放到桶中
for (int i = 0; i < arrNum; i++) {
// 判断该元素应该放入哪个桶中：当前元素减去最小值，乘以桶数量减一，再除以最大值减最小，得到的值就是桶编号
int num = (int)((arr[i] - min) * (arrNum - 1) / (max - min));
buckets.get(num).add(arr[i]);
}
// 对每个桶内部进行排序
for (int i = 0; i < buckets.size(); i++) {
Collections.sort(buckets.get(i));
}
// 最后遍历桶，输出所有元素
int i = 0;
for (LinkedList<Double> bucket : buckets){
for (double num : bucket){
arr[i++] = num;
}
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录