排序算法 - 9桶排序 - 《数据结构/算法》

https://www.yduba.com/biancheng-7382573665.html
桶排序或所谓的箱排序的原理是将数组分到有限数量的桶子里，然后对每个桶子再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后将各个桶中的数据有序的合并起来。
假设有一组长度为N的待排序关键字序列K[1…n]。首先将这个序列划分成M个的子区间（桶）。然后基于某种映射函数，将待排序序列的关键字K映射到第i个桶中（即桶数组B的下标i），那么该关键字k就作用B[i]中的元素（每个桶B[i]都是一组大小为N/M的序列）。接着对每个桶B[i]中的所有元素进行比较排序（可以使用快速排序）。然后依次枚举输出B[0]…B[M]中的全部内容即是一个有序序列。
映射函数：bindex = f(k) 其中，bindex 为桶数组B的下标(即第bindex个桶)，k为待排序列的关键字。桶排序之所以能够高效，其关键在于这个映射函数，它必须做到：如果关键字k1 < k2，那么f(k1) <= f(k2)。也就是说B(i)中的最小数据都要大于B(i-1)中最大数据。很显然，映射函数的确定与数据本身的特点有很大的关系，我们下面举个例子：
假如待排序列K= {49、 38 、 35、 97 、 76、 73 、 27、 49 }。这些数据全部在1—100之间。因此我们定制10个桶，然后确定映射函数f(k)=k/10。则第一个关键字49将定位到第4个桶中(49/10=4)。依次将所有关键字全部堆入桶中，并在每个非空的桶中进行快速排序后得到如下图所示：
9桶排序 - 图1
对上图只要顺序输出每个B[i]中的数据就可以得到有序序列了。
算法步骤
1. 假设待排序的一组数统一的分布在一个范围中，并将这一范围划分成几个子范围，也就是桶。
2. 将待排序的一组数，分档规入这些子桶，并将桶中的数据进行排序。
3. 将各个桶中的数据有序的合并起来。

效率分析
桶排序利用函数的映射关系，减少了几乎所有的比较工作。实际上，桶排序的f(k)值的计算，其作用就相当于快排中划分，已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做先进的比较排序即可。
对N个关键字进行桶排序的时间复杂度分为两个部分：
a )、循环计算每个关键字的桶映射函数，这个时间复杂度是O(N)。
b )、利用先进的比较排序算法对每个桶内的所有数据进行排序，其时间复杂度为∑O(Ni * logNi) 。其中 Ni为第i个桶的数据量。
很显然，第b部分是桶排序性能好坏的决定因素。尽量减少桶内数据的数量是提高效率的唯一办法(因为基于比较排序的最好平均时间复杂度只能达到O(N*logN)了)。因此，我们需要尽量做到下面两点：
a )、映射函数f(k)能够将N个数据平均的分配到M个桶中，这样每个桶就有[N/M]个数据量。
b )、尽量的增大桶的数量。极限情况下每个桶只能得到一个数据，这样就完全避开了桶内数据的“比较”排序操作。当然，做到这一点很不容易，数据量巨大的情况下，f(k)函数会使得桶集合的数量巨大，空间浪费严重。这就是一个时间代价和空间代价的权衡问题了。
对于N个待排数据，M个桶，平均每个桶[N/M]个数据的桶排序平均时间复杂度为：O(N)+O(M(N/M)log(N/M))=O(N+N(logN-logM)) = O(N+NlogN-N*logM)
当N=M时，即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。
总结：桶排序的平均时间复杂度为线性的O(N+C)，其中C=N*(logN-logM)。如果相对于同样的N，桶数量M越大，其效率越高，最好的时间复杂度达到O(N)。当然桶排序的空间复杂度为O(N+M)，如果输入数据非常庞大，而桶的数量也非常多，则空间代价无疑是昂贵的。

算法稳定性
桶排序中，假如升序排列，a已经在桶中，b插进来是永远都会a右边的(因为一般是从右到左，如果不小于当前元素，则插入改元素的右侧)，所以桶排序是稳定的。

动图演示
9桶排序 - 图2

代码实现

<?php
function bucketSort($max, $array)
{
    //填充木桶
    $arr = array_fill(0, $max+1, 0);
    //开始标示木桶
    for($i = 0; $i <= count($array)-1 ; $i++)
    {
        $arr[$array[$i]] ++;
    }
    $mutomg = array();
    //开始从木桶中拿出数据
    for($i = 0; $i <= $max; $i ++)
    {
        for($j = 1; $j <= $arr[$i]; $j ++)
        { //这一行主要用来控制输出多个数字
            $mutong[] = $i;
        }
    }
    return $mutong;
}