排序算法系列(10)——桶排序

本节继续进行分配排序中的最后一个算法：桶排序，这也是本期10大排序中的最后一个排序算法，本算法放在最后主要是有两个目的：1. 经历了翻山越岭地前9个排序算法的学习，想必大家是累了吧（反正我累了，不接受反驳），桶排序就是给大家调剂用的，我觉得其思想真的是格外简单（核心逻辑）；2. 就是本排序一般不会作为面试内容（如若出了此类题目，就当我放*，狗头保命，手动滑稽）

好了，闲聊结束，开始进行桶排序的逻辑梳理：

1. 获取数组最大值max和最小值min: 桶的数量num = (max-min) / array.length + 1
2. 在[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，来进行桶区间划分。
3. 2中的每个区间都是一个桶，遍历array中元素，将每个元素分配到对应的区间桶中
4. 对每个区间(桶)内的元素进行排序，然后依次合并每个区间的数据，赋值到原数组，最终得到排序结果

逻辑很简单，比基数排序还要简单，而且桶内排序还是那句话，择您所好。值得需要讲一下的是桶数量的确定：

具体为什么取值为上述表达式，我也并不能给出一个很好的解释(烦请百度)，但是我能从一些角度来揣摩一下这样设置的意图：

1. (max-min)/array.length能整除，那就其实num=整除的数字也无可厚非，但是这样分桶的时候，最后一个桶的区间就为[min+(num-1)range, min+numrange)，此时 num*range+min == max，若为左闭右开区间的话，max值就不能放进最后一个桶了，所以还是需要额外有一个桶~
2. 确定了桶数量num后，其实range = (max - min) / num，对于整数情形描述还是不太合理的：
   非整除情况range其实比实际的浮点运算会小一些的，这样range如上述计算最终的区间划分依然可能覆盖不到max元素
   因此实践中取array.length作为range值进行桶区间划分
   

以上只是我自身的一些感悟罢了，细究可能我也就跪了，下面直接上代码，让我们愉快的结束最后一个排序算法的学习~

    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!