基于PHP实现计数排序的步骤和思路是怎样
计数排序只适合使用在键的变化不大于元素总数的情况下。它通常用作另一种排序算法（基数排序）的子程序，这样可以有效地处理更大的键。
总之，计数排序是一种稳定的线性时间排序算法。计数排序使用一个额外的数组C ，其中第i个元素是待排序数组 A中值等于 i的元素的个数。然后根据数组C 来将A中的元素排到正确的位置。
通常计数排序算法的实现步骤思路是：
1.找出待排序的数组中最大和最小的元素；
2.统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
3.对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
4.反向填充目标数组：将每个元素i放在新数组的第C[i]项，每放一个元素就将C[i]减去1。
PHP计数排序算法的实现代码示例如下：
?php
function counting_sort($my_array, $min, $max)
{
$count = array();
for($i = $min;
$i = $max;
$i++)
{
$count[$i] = 0;
}
foreach($my_array as $number)
{
$count[$number]++;
}
$z = 0;
for($i = $min;
$i = $max;
$i++) {
while( $count[$i]-- >
0 ) {
$my_array[$z++] = $i;
}
}
return $my_array;
}
$test_array = array(3, 0, 2, 5, -1, 4, 1);
echo "原始数组 :\n";
echo implode(', ',$test_array );
echo "\n排序后数组\n:";
echo implode(', ',counting_sort($test_array, -1, 5)). PHP_EOL;
输出：
原始数组 : 3, 0, 2, 5, -1, 4, 1
排序后数组 :-1, 0, 1, 2, 3, 4, 5
下面补充一个例子
1、计数排序只适用于整数在小范围内排序
?php
$arr = [95,94,91,98,99,90,99,93,91,92];
function countSort($arr){
$max = $arr[0];
$min = $arr[0];
for($i=0;
$icount($arr);
$i++){
if($arr[$i]>
$max){
$max = $arr[$i];
}
if($arr[$i] $min){
$min = $arr[$i];
}
}
try{
$frequency = new SplFixedArray($max-$min+1);
for($i=0;
$icount($arr);
$i++){
if(empty($frequency[$arr[$i]-$min]))
$frequency[$arr[$i]-$min] = 0;
$frequency[$arr[$i]-$min] += 1;
}
$sum = 0;
for ($i=0;
$i count($frequency);
$i++) {
$sum += $frequency[$i];
$frequency[$i] = $sum;
}
$splfixed = new SplFixedArray(count($arr));
for($i=(count($arr)-1);
$i>
=0;
$i--){
$splfixed[$frequency[$arr[$i]-$min]-1] = $arr[$i];
$frequency[$arr[$i]-$min] -= 1;
}
}
catch(RuntimeException $re){
echo "RuntimeException: ".$re->
getMessage()."\n";
}
print_r($splfixed->
toArray());
}
countSort($arr);
?>
输出
Array
(
[0] =>
90
[1] =>
91
[2] =>
91
[3] =>
92
[4] =>
93
[5] =>
94
[6] =>
95
[7] =>
98
[8] =>
99
[9] =>
99
)
2、php计数排序
获取序列中的最小值min和最大值max O(n)
统计min - max之间所有值在序列中的出现次数 O(n)
顺序输出min - max的所有值,次数为0不输出,其余次数为多少就输出多少 O(k) k为数据范围
例如序列为: 2, 4, 6, 9, 4, 8
min = 2, max = 9, n为6,k为8
统计出现次数为
[2 => 1, 3 => 0, 4 => 2, 5 => 0, 6 => 1, 7 => 0, 8 => 1, 9 => 1]
输出结果为
2, 4, 4, 6, 8, 9
很明显,计数排序的复杂度为O(n) + O(k),也就是和数据量和数据范围有关.
若n和k相近,则可认为是O(n)
同时,因为要统计出现次数,如果数据范围过大而数据又很稀疏,造成的空间浪费比较大
class CountSort
{
private $originalData = [];
private $rangeMap = [];
private $resultData = [];
public function __construct($original = [])
{
$this->
originalData = $original;
}
public function sort()
{
list($min, $max) = $this->
calculateDataRange();
$this->
statisticNumberOfOccurrence($min, $max);
$this->
resultData = $this->
generateResult();
return $this->
resultData;
}
protected function calculateDataRange()
{
$max = null;
$min = null;
foreach ($this->
originalData as $value) {
if (!is_null($max)) {
if ($value >
$max) {
$max = $value;
}
}
else {
$max = $value;
}
if (!is_null($min)) {
if ($value $min) {
$min = $value;
}
}
else {
$min = $value;
}
}
return [$min, $max];
}
protected function statisticNumberOfOccurrence($min, $max)
{
for ($i = $min;
$i = $max;
$i++) {
$this->
rangeMap[$i] = 0;
}
foreach ($this->
originalData as $value) {
$this->
rangeMap[$value]++;
}
}
protected function generateResult()
{
$result = [];
foreach ($this->
rangeMap as $key =>
$value) {
if ($value != 0) {
for ($i = 0;
$i $value;
$i++) {
array_push($result, $key);
}
}
}
return $result;
}
}
$testData = [2, 3, 4, 3, 10, 30, 20, 15, 10, 12, 33];
$countSort = new CountSort($testData);
echo 'pre>
';
var_dump($countSort->
sort());
输出
pre>
array(11) {
[0]=>
int(2)
[1]=>
int(3)
[2]=>
int(3)
[3]=>
int(4)
[4]=>
int(10)
[5]=>
int(10)
[6]=>
int(12)
[7]=>
int(15)
[8]=>
int(20)
[9]=>
int(30)
[10]=>
int(33)
}
以上就是关于基于PHP实现计数排序的步骤和思路是怎样的介绍啦，需要的朋友可以参考上述内容，希望对大家有帮助，想要了解更多，欢迎关注网络，小编将为大家输出更多高质量的实用文章！
声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！
若转载请注明出处： 基于PHP实现计数排序的步骤和思路是怎样
本文地址： https://pptw.com/jishu/650371.html