原理

基数排序与计数排序的思路类似，在计数排序的基础上增加了桶的使用。基数排序一般用于对正整数的排序，排序过程中先根据个位进行分桶，将数字插入到基数 0-9 的各个桶中，接着顺序取出，这样就对个位排好序了，然后再根据十位上的数字依次插入到 0-9 的桶中，接着顺序取出，直到排到最高位。

步骤

1. 首先循环原始数组，得到每一个数的个位，按照个位的数字分别插入到 0-9 的桶中。
2. 接着从 0-9 的数组中依次顺序取出所有数字，此时个位就排好序了。
3. 使用同样的逻辑再得到每个数的十位，按照十位数字的大小分别插入到 0-9 的数组中，接着从 0-9 的数组中依顺序取出，此时十位也排好序了。
4. 以此类推，直到最高位。

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

代码

复制
<?php declare(strict_types=1);
 
class Algorithm
{
    public function radixSort(array $s, int $m = 1): array
    {
        $map = [];
        $i = 10;
        $j = 1;
        while ($m--) { // 需要排的位数 
            foreach ($s as $v) {
                $k = intval($v % $i / $j); // 取得某一个位的数 
                isset($map[$k]) ? ($map[$k][] = $v) : ($map[$k] = [$v]);
            }
 
            $c = 0;
            for ($k = 0; $k < 10; $k++) {
                while (!empty($map[$k])) {
                    $s[$c] = array_shift($map[$k]);
                    $c++;
                }
            }
 
            $i *= 10;
            $j *= 10;
        }
 
        return $s;
    }
}

时间复杂度

总共三个循环，自外层是位数循环 m，里面分别是数组个数 n 以及 0-9 的桶 k：O((n+k)m)

最好情况（每个桶中不超过1个数字）：O((n+k)m)

最坏情况（所有元素都集中到一个桶中）：O((2n+k)m)

空间复杂度

需要 k 个桶，所有桶累计存储 n 个数：O(n+k)