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

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

动图演示

代码实现：

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;
}