桶排序

研究一位大神写，有一点没有明白，然后就去其他地方觅食，明白了其中的原理，根据原理整理写下：

/**
 * @param array $arr 待排序的数组
 * @return array $sort_result_arr 排序后的数组
 */
function bucketSorting(array $arr):array
{
    //待排序数组中的最小值与最大值
    $min=min($arr);
    $max=max($arr);

    //生成最小key为$min,最大key为$max-$min+1数组，且每个key对应的value值都为0
    //$bucket数组就相当于一个大桶，每个key对应一个型号桶，value值对应此型号桶的数量
    $bucket = array_fill($min, $max-$min+1, 0);

    //将$arr的值放入对应的型号桶中。（将$arr中的value对应$bucket的key）
    foreach($arr as $value){
        //计算对应型号桶的数量
        $bucket[$value]++;
    }

    //因为上面的步骤已经将$arr中的value值放在对应$bucket的key，按照大小排好了。所以下面只要按照类型桶的个数显示几个
    $sort_result_arr = array();
    foreach ($bucket as $k=>$v){
        //按照类型桶的个数显示几个
        for($i=1;$i<=$v;$i++){
            $sort_result_arr[]=$k;
        }
    }
    return $sort_result_arr;
}

$arr = array(3,1,33,45,6,3,5,3,5);
$sort_result_arr = bucketSorting($arr);
var_dump($sort_result_arr);

本作品采用《CC 协议》，转载必须注明作者和本文链接