桶排序

---

桶排序(Bucket Sort)

桶排序是计数排序的升级版。 它利用了函数的映射关系，高效与否的关键就在于这个映射函数来确定。 桶排序(Bucket Sort)的工作原理： 假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序 (有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排);

算法描述

• 设置一个定量的数组当作空桶；
• 遍历输入数据，并且把数据一个一个放到对应的桶里去；
• 对每个不是空的桶进行排序；
• 从不是空的桶里把排好序的数据拼接起来。

图片演示

代码实现

$arr = [20, 40, 60, 80, 30, 70, 90, 10, 50, 0, 5];
//$arr = [3, 2, 4, 1, 5, 9, 0, 0];

const BUCKET_SIZE = 5; // 桶分配规则

/**
 * @param $arr
 * @return mixed
 * 桶排序
 */
function bucketSort(&$arr)
{
    $arrSize = count($arr); // 大小,数组
    $minValue = min($arr); // 最小值,数组
    $maxValue = max($arr); // 最大值,数组
    $bucketCount = floor(($maxValue - $minValue) / BUCKET_SIZE) + 1; // 桶数量,用映射函数确定
    $buckets = array_fill(0, $bucketCount, 0); // 桶数组,建立额外存储空间
    // 桶初始化
    for ($i = 0; $i < count($buckets); $i++) {
        $buckets[$i] = [];
    }
    // 桶映射,用映射函数将数据分配到各个桶中
    for ($i = 0; $i < $arrSize; $i++) {
        array_push($buckets[floor(($arr[$i] - $minValue) / BUCKET_SIZE)], $arr[$i]);
    }

    $index = 0; // 哨兵
    for ($i = 0; $i < $bucketCount; $i++) {
        // 将各桶数据进行插入排序
        insertionSort($buckets[$i]);
        // 将桶数据出栈
        for ($j = 0; $j < count($buckets[$i]); $j++) {
            $arr[$index++] = $buckets[$i][$j];
        }
    }
}

/**
 * @param $arr
 * 插入排序
 */
function insertionSort(&$arr)
{
    $arrSize = count($arr); // 大小,数组
    for ($i = 1; $i < $arrSize; $i++) {
        $current = $arr[$i]; // 当前元素放到暂存区
        $preIndex = $i - 1; // 坐标,前一个元素

        // 右移所有大于当前元素的元素
        while ($preIndex >= 0 && $arr[$preIndex] > $current) {
            $arr[$preIndex + 1] = $arr[$preIndex];
            $preIndex--;
        }
        $preIndex++; // 补偿,退出循环条件使坐标变成了前前一个元素

        $arr[$preIndex] = $current; // 插入到正确位置
    }
}

bucketSort($arr);
var_dump($arr);

算法分析

桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决于对各个桶之间数据进行排序的时间复杂度， 因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。