PHP实现-计数排序
2018-03-20 14:53 By
"Powerless"
3461
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
-
初识七层、五层、四层网络协议 Posted on 2021-04-09 16:52
-
投票通过，PHP 8 确认引入 Union Types 2.0 Posted on 2019-11-18 22:22
-
Linux工具 - NM目标文件格式分析 Posted on 2019-04-24 10:29
-
PHP扩展安装 Posted on 2019-06-24 11:28
-
Redis各种数据类型的使用场景举例分析【三】 Posted on 2018-11-22 17:00
-
ACID原则 Posted on 2020-12-17 16:36
-
PHP7不兼容性 Posted on 2018-03-07 15:59
-
MySQL分组 Posted on 2019-11-18 14:00
评 论