桶排序（Bucket Sort）
1.什么是桶排序
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
- 在额外空间充足的情况下，尽量增大桶的数量
- 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
2.算法解释
- 什么时候最快
当输入的数据可以均匀的分配到每一个桶中。
- 什么时候最慢
当输入的数据被分配到了同一个桶中。
- 示意图元素分布在桶中：
然后，元素在每个桶中排序：
3.代码实现
public class BucketSort { public static void main(String[] args) { //初始化数组 int[] arr = {5, 3, 1, 4, 2, 7, 8, 6, 10, 9}; bucketSort(arr); } 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<>()); } //将每个元素放入桶 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)); } System.out.println(bucketArr.toString()); } }
4.输出结果
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
