10大经典排序算法之桶排序(PHP版)

发布时间:2020/11/23 作者:天马行空 阅读(169)

桶排序 ,是一个排序算法,工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。对于数组中的元素分布均匀的情况,排序效率较高,相反的,如果分布不均匀,则会导致大部分的数落入到同一个桶中,使效率降低。


算法步骤
1、找出最大值,最小值。
2、根据数组的长度,创建出若干个桶。
3、遍历数组的元素,根据元素的值放入到对应的桶中。
4、对每个桶的元素进行排序(可使用快排,插入排序等)。
5、按顺序合并每个桶的元素,排序完成。


动图演示

20190219081232815.png


代码实现:

function bucketSort($arr, $bucketSize = 5)
{
    if (count($arr) === 0) {
        return $arr;
    }
    
    // 找出其中的最大值和最小值
    $minValue = $arr[0];
    $maxValue = $arr[0];
    for ($i = 1; $i < count($arr); $i ++) {
        if ($arr[$i] < $minValue) {
            $minValue = $arr[$i];
        } else if ($arr[$i] > $maxValue) {
            $maxValue = $arr[$i];
        }
    }
    
    // 按照跨度生成空桶
    $bucketCount = floor(($maxValue - $minValue) / $bucketSize);
    $buckets = array();
    for ($i = 0; $i < $bucketCount; $i ++) {
        $buckets[$i] = [];
    }
    
    // 往空桶里面填充数据
    for ($i = 0; $i < count($arr); $i ++) {
        $buckets[floor(($arr[$i] - $minValue) / $bucketSize)][] = $arr[$i];
    }
    
    // 循环桶,对每一个桶进行排序
    $arr = array();
    for ($i = 0; $i < count($buckets); $i ++) {
        $bucketTmp = $buckets[$i];
        // sort($bucketTmp);
        $bucketTmp = $this->charu($bucketTmp);
        for ($j = 0; $j < count($bucketTmp); $j ++) {
            $arr[] = $bucketTmp[$j];
        }
    }
    
    return $arr;
}



关键字php 算法