原理
基数排序与计数排序的思路类似,在计数排序的基础上增加了桶的使用。基数排序一般用于对正整数的排序,排序过程中先根据个位进行分桶,将数字插入到基数 0-9
的各个桶中,接着顺序取出,这样就对个位排好序了,然后再根据十位上的数字依次插入到 0-9
的桶中,接着顺序取出,直到排到最高位。
步骤
- 首先循环原始数组,得到每一个数的个位,按照个位的数字分别插入到
0-9
的桶中。 - 接着从
0-9
的数组中依次顺序取出所有数字,此时个位就排好序了。 - 使用同样的逻辑再得到每个数的十位,按照十位数字的大小分别插入到
0-9
的数组中,接着从0-9
的数组中依顺序取出,此时十位也排好序了。 - 以此类推,直到最高位。
此图来自: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)