4分钟学会桶排序

桶排序算法思想

    桶排序思想就是把区间划分为n个大小相同的子区间，这样的子区间称为桶。然后将区间的每个元素按区间范围分到各个桶中去。每一个桶再分个排序，然后按照次序把每个桶中的元素依次取出来，就能把区间排完序。桶排序的时间复杂度和空间复杂度都是O(n)，桶排序是一种稳定的排序算法。但是桶排序的性能并非是绝对稳定的，因为如果元素分布不均衡，比如说创建了100个桶，大多数元素都集中在了第1个桶，这样桶排序的时间复杂度就会退化为O(n logn)，而且还浪费了空间。

一个例子带你了解桶排序

    假设有一个序列，我们对此序列进行桶排序。首先，我们创建桶，桶的数量一般取原始序列的元素数量。最后一个桶一般放序列中的最大值，区间划分除去最后存放最大元素的那个桶，其他桶按照比例确定区间范围。

    计算公式为：区间范围 = (序列最大值 - 序列最小值) / (桶的数量 - 1)

假设待排序序列为：23，56，80，63，25，20，10，36

    按照公式，每个区间范围 = (最大值80 - 最小值10) / (桶的数量8 - 1) = 10

    划分好每个桶存放数据的区间范围后，我们遍历序列，把符合条件的元素放入桶中。

把序列的所有元素放入桶之后，分别对每个桶里面的元素进行排序，排完序后如下图所示。

最后依次把每个桶中的元素输出，输出的序列即为排完序的序列。

桶排序算法代码实现(Java版本)

// 链表实现public double[] bucketSort(double[] array) {    // 定义变量存放数组的最小值和最大值，初始化为数组第一个元素    double min = array[0];    double max = array[0];    // 遍历序列找出数组最小值和最大值    for (int i = 1; i < array.length; ++i) {        if (max < array[i])            max = array[i];        if (array[i] < min)            min = array[i];    }    // 数组最大值和最小值的差值    double d = max - min;
    // 初始化桶的个数为序列元素个数    int bucketNumber = array.length;    // 桶列表    List<LinkedList<Double>> bucketList = new ArrayList<>(bucketNumber);    // 初始化桶    for (int i = 0; i < bucketNumber; ++i)        bucketList.add(new LinkedList<>());
    // 遍历数组中的元素，把所有元素都放入对应的桶当中    for (int i = 0; i < array.length; i++) {        // 计算当前元素应该放在哪个桶里面        int num = (int)((array[i] - min) / (d / (bucketNumber - 1)));        // 把当前元素放入桶中        bucketList.get(num).add(array[i]);    }
    // 桶内元素排序    for (int i = 0; i < bucketNumber; ++i)        Collections.sort(bucketList.get(i));
    // 写入原数组    int k = 0;    for (LinkedList<Double> doubles : bucketList)        for (Double x : doubles) {            array[k] = x;            ++k;        }        // 返回排完序的数组    return array;}