八、基数排序

PHP技术
538
0
0
2022-10-14
标签   PHP排序

原理

基数排序与计数排序的思路类似,在计数排序的基础上增加了桶的使用。基数排序一般用于对正整数的排序,排序过程中先根据个位进行分桶,将数字插入到基数 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 的桶 kO((n+k)m)

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

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

空间复杂度

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