桶排序（Bucket Sort）

1.什么是桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的要害就在于这个映射函数的确定。为了使桶排序更加高效，咱们须要做到这两点：

  1. 在额定空间短缺的状况下，尽量增大桶的数量
  2. 应用的映射函数可能将输出的 N 个数据平均的调配到 K 个桶中

同时，对于桶中元素的排序，抉择何种比拟排序算法对于性能的影响至关重要。

2.算法解释

  1. 什么时候最快

    当输出的数据能够平均的调配到每一个桶中。

  2. 什么时候最慢

    当输出的数据被调配到了同一个桶中。

  3. 示意图

    元素散布在桶中：

    而后，元素在每个桶中排序：

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]