桶排序及其应用
- 2019 年 11 月 6 日
- 筆記
一、思想
一句话总结：
划分多个范围相同的区间，每个自区间自排序，最后合并。
桶排序是计数排序的扩展版本，计数排序可以看成每个桶只存储相同元素，而桶排序每个桶存储一定范围的元素，通过映射函数，将待排序数组中的元素映射到各个对应的桶中，对每个桶中的元素进行排序，最后将非空桶中的元素逐个放入原序列中。
桶排序需要尽量保证元素分散均匀，否则当所有数据集中在同一个桶中时，桶排序失效。
二、图解过程
三、核心代码
public static void bucketSort(int[] arr){ // 计算最大值与最小值 int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for(int i = 0; i < arr.length; i++){ max = Math.max(max, arr[i]); min = Math.min(min, arr[i]); } // 计算桶的数量 int bucketNum = (max - min) / arr.length + 1; ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum); for(int i = 0; i < bucketNum; i++){ bucketArr.add(new ArrayList<Integer>()); } // 将每个元素放入桶 for(int i = 0; i < arr.length; i++){ int num = (arr[i] - min) / (arr.length); bucketArr.get(num).add(arr[i]); } // 对每个桶进行排序 for(int i = 0; i < bucketArr.size(); i++){ Collections.sort(bucketArr.get(i)); } // 将桶中的元素赋值到原序列 int index = 0; for(int i = 0; i < bucketArr.size(); i++){ for(int j = 0; j < bucketArr.get(i).size(); j++){ arr[index++] = bucketArr.get(i).get(j); } } }
四、复杂度分析
时间复杂度：O(N + C) 对于待排序序列大小为 N，共分为 M 个桶，主要步骤有：
N 次循环，将每个元素装入对应的桶中
M 次循环，对每个桶中的数据进行排序（平均每个桶有 N/M 个元素）
一般使用较为快速的排序算法，时间复杂度为 O(NlogN)O(NlogN)O(NlogN)，实际的桶排序过程是以链表形式插入的。
整个桶排序的时间复杂度为：
O(N)+O(M∗(N/M∗log(N/M)))=O(N∗(log(N/M)+1))O(N)+O(M*(N/M*log(N/M)))=O(N*(log(N/M)+1))O(N)+O(M∗(N/M∗log(N/M)))=O(N∗(log(N/M)+1))
当 N = M 时，复杂度为 O(N)O(N)O(N)
额外空间复杂度：O(N + M)
五、稳定性分析
桶排序的稳定性取决于桶内排序使用的算法。
六、实际案例
案例一：
一年的全国高考考生人数为500 万，分数使用标准分，最低100 ，最高900 ，没有小数，要求对这500 万元素的数组进行排序。
分析：对500W数据排序，如果基于比较的先进排序，平均比较次数为O(5000000*log5000000)≈1.112亿。但是我们发现，这些数据都有特殊的条件： 100=<score<=900。那么我们就可以考虑桶排序这样一个“投机取巧”的办法、让其在毫秒级别就完成500万排序。
方法：创建801(900-100)个桶。将每个考生的分数丢进f(score)=score-100的桶中。这个过程从头到尾遍历一遍数据只需要500W次。然后根据桶号大小依次将桶中数值输出，即可以得到一个有序的序列。而且可以很容易的得到100分有***人，501分有***人。
实际上，桶排序对数据的条件有特殊要求，如果上面的分数不是从100-900，而是从0-2亿，那么分配2亿个桶显然是不可能的。所以桶排序有其局限性，适合元素值集合并不大的情况。
案例二：
在一个文件中有 10G 个整数，乱序排列，要求找出中位数。
内存限制为 2G。只写出思路即可（内存限制为 2G的意思就是，可以使用2G的空间来运行程序，而不考虑这台机器上的其他软件的占用内存）。这问题可以使用桶排序，当然还有其他更好的方案，下次再讲。
