原理

计数排序适用于特定条件下的排序：1. 排序内容在一定范围 k 内，如 1-1000 之间的整数；2. 并且元素之间有固定的步长。

对于满足上述条件的数据可以将排序内容先循环一遍，建立一个键值对映射，键为需要排序的元素，值为此元素出现的个数，最后将映射中的内容输出为有序数组即可。

步骤

1. 首先循环原数组，以元素为键，出现的次数为值，存入到映射中。
2. 接着循环 k 次，从映射中依次取出元素放入数组，排序完成。

此图来自：runoob.com 计数排序

代码

<?php declare(strict_types=1);

class Algorithm
{
    public function countingSort(array $s, int $max, int $min = 0, int $gap = 1): array{
        $map = [];
        foreach ($s as $i) {
            $map[$i] = ($map[$i] ?? 0) + 1;
        }

        $arr = [];
        for ($i = $min; $i <= $max; $i += $gap) {
            while (!empty($map[$i])) {
                $arr[] = $i;
                $map[$i]--;
            }
        }

        return $arr;
    }
}

时间复杂度

两个循环：O(n+k)

最好情况（数组没有重复的元素）：O(n+k)

最坏情况（数组中全是重复元素）：O(2n+k)

空间复杂度

需要新建一个映射数组：O(k)