PHP实现-计数排序
2018-03-20 14:53 By
"Powerless"
3364
0
0
思路分析
计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序
/**
* 计数排序
* @param $arr
* @return array
*/
function countingSort($arr)
{
$len = count( $arr );
if( $len <= 1 ) return $arr;
// 找出待排序的数组中最大值和最小值
$min = min($arr);
$max = max($arr);
// 计算待排序的数组中每个元素的个数
$countArr = array();
for($i = $min; $i <= $max; $i++)
{
$countArr[$i] = 0;
}
foreach($arr as $v)
{
$countArr[$v] += 1;
}
$resArr = array();
foreach ($countArr as $k=>$c) {
for($i = 0; $i < $c; $i++)
{
$resArr[] = $k;
}
}
return $resArr;
}
小结：
时间复杂度：O(n + k)
空间复杂度：O(k)
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。
作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
计数排序属于稳定排序
View in WeChat
Others Discussion
-
MySQL分组 Posted on 2019-11-18 14:00
-
PHP7不兼容性 Posted on 2018-03-07 15:59
-
一些常见的基础概念 Posted on 2018-11-28 19:10
-
HTTP头中隐藏PHP版本号 Posted on 2021-01-11 16:38
-
QPS、TPS、RT、吞吐量到底是什么 Posted on 2020-02-02 01:15
-
MySQL事务介绍 Posted on 2019-06-05 18:14
-
能创建多少个 TCP 连接？ Posted on 2021-08-02 16:00
-
MySQL中的行级锁,表级锁,页级锁 Posted on 2018-08-25 11:00
评 论