PHP实现-计数排序
2018-03-20 14:53 By
"Powerless"
3393
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 2018-08-25 11:00
-
MySQL分组 Posted on 2019-11-18 14:00
-
PHP练习-爬楼梯问题 Posted on 2020-08-14 23:56
-
PHP8.1 性能基准测试 Posted on 2022-10-08 17:40
-
MySQL事务介绍 Posted on 2019-06-05 18:14
-
必学十大经典排序算法，看这篇就够了 Posted on 2019-11-18 16:30
-
巧用CAS解决数据一致性问题 Posted on 2019-03-07 11:55
-
PHP练习-无重复字符的最长子串 Posted on 2020-09-17 18:03
评 论