本节继续进行分配排序中的最后一个算法：桶排序，这也是本期10大排序中的最后一个排序算法，本算法放在最后主要是有两个目的：1. 经历了翻山越岭地前9个排序算法的学习，想必大家是累了吧（反正我累了，不接受反驳），桶排序就是给大家调剂用的，我觉得其思想真的是格外简单（核心逻辑）；2. 就是本排序一般不会作为面试内容（如若出了此类题目，就当我放*，狗头保命，手动滑稽）
好了，闲聊结束，开始进行桶排序的逻辑梳理：
- 获取数组最大值max和最小值min: 桶的数量num = (max-min) / array.length + 1
- 在[min, max]之间的区域范围，平均划为num个统计区间，每个区间的范围大小为：range= (max-min) / num可简单表示为：
[min, min+range)，[min+range, min+2*range)......，[min+(num-1)*range, min+num*range)
实践中往往采用range = array.length，来进行桶区间划分。- 2中的每个区间都是一个桶，遍历array中元素，将每个元素分配到对应的区间桶中
- 对每个区间(桶)内的元素进行排序，然后依次合并每个区间的数据，赋值到原数组，最终得到排序结果
逻辑很简单，比基数排序还要简单，而且桶内排序还是那句话，择您所好。值得需要讲一下的是桶数量的确定：
具体为什么取值为上述表达式，我也并不能给出一个很好的解释(烦请百度)，但是我能从一些角度来揣摩一下这样设置的意图：
- (max-min)/array.length能整除，那就其实num=整除的数字也无可厚非，但是这样分桶的时候，最后一个桶的区间就为[min+(num-1)range, min+numrange)，此时 num*range+min == max，若为左闭右开区间的话，max值就不能放进最后一个桶了，所以还是需要额外有一个桶~
- 确定了桶数量num后，其实range = (max - min) / num，对于整数情形描述还是不太合理的：
非整除情况range其实比实际的浮点运算会小一些的，这样range如上述计算最终的区间划分依然可能覆盖不到max元素
因此实践中取array.length作为range值进行桶区间划分
%20*%20array.length%20%5Cgt%20max)
以上只是我自身的一些感悟罢了，细究可能我也就跪了，下面直接上代码，让我们愉快的结束最后一个排序算法的学习~
public void bucketSort(int[] arrays) {
if (arrays.length <= 1) {
return;
}
// 数据在每个桶中分布越均匀，桶排序效果越好
int max = Arrays.stream(arrays).max().getAsInt();
int min = Arrays.stream(arrays).min().getAsInt();
if (max == min) {
return;
}
//桶的数量=(max-min)/arrays.length+1记住即可
//可得桶的范围大小大概是arrays.length
int bucketNum = (max - min) / arrays.length + 1;
List<List<Integer>> buckets = new ArrayList<>(bucketNum);
for (int i = 0; i < bucketNum; i++) {
buckets.add(new ArrayList<>());
}
//遍历数组确定放在哪个桶里
for (int i = 0; i < arrays.length; i++) {
int bucketIndex = (arrays[i] - min) / arrays.length;
buckets.get(bucketIndex).add(arrays[i]);
}
//每个桶内部排序
buckets.stream().forEach(Collections::sort);
//然后buckets的每个list展开为stream合并
List<Integer> result = buckets.stream().flatMap(List::stream).collect(Collectors.toList());
//赋值到原数组
for (int i = 0; i < arrays.length; i++) {
arrays[i] = result.get(i);
}
}
Stay hungry,Stay foolish!
Keep going!
