七、计数排序
21 / 0 / 创建于 1年前
xiaer 的个人博客
原理
计数排序适用于特定条件下的排序：1. 排序内容在一定范围 k 内，如 1-1000 之间的整数；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)
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号