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

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

计数排序,是一个非基于比较的排序算法。它的优势在于在对一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中k是整数的范围),快于任何比较排序算法。


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


动图演示

countingSort.gif


代码实现:

public function countingSort($arr)
{
    $maxValue = max($arr);
    // 数据跨度有多大就生成多少个空桶
    for ($m = 0; $m < $maxValue + 1; $m ++) {
        $bucket[] = null;
    }
    
    $arrLen = count($arr);
    // 对空桶进行计数
    for ($i = 0; $i < $arrLen; $i ++) {
        if (! array_key_exists($arr[$i], $bucket)) {
            $bucket[$arr[$i]] = 0;
        }
        $bucket[$arr[$i]] ++;
    }
    
    $sortedIndex = 0;
    // 按照桶的顺序取数据,生成一个新的有序数组
    foreach ($bucket as $key => $len) {
        if ($len !== null) {
            for ($j = 0; $j < $len; $j ++) {
                $arr[$sortedIndex ++] = $key;
            }
        }
    }
    
    return $arr;
}



关键字php 算法