思路

给定一个数组，内容都为数字
获取数组内最大值(可使用max()函数或for循环判断)
初始化一个长度为最大值减一的数组与一个存放计数的数组
循环遍历整个输入的数组
1. 若在计数数组中存在一个键名为循环中当前数组值的键
  1. 计数数组该键值加一
2. 若不存在
  1. 计数数组该键值为一
从0开始遍历计数数组
1. 若当前键的值不为空
  1. 循环当前键对应的值次，添加此键名至原数组
遍历计数数组结束
得到一个升序数组

代码

<?php

$array = array(1,2,1,1,1,1,1,1,2,5,3,45,2,25,3,22,3,3,4,4,4,4,4,23,23,42,3,22,2,3,4,23,4,234,32,2,2,3,1,1,1);

function countingSort($arr)
{
    
    //初始化数组，请求空间
    for ($m = 0; $m < max($arr) + 1; $m++) {
        $bucket[] = null; //元素设为null
    }

    $arrLen = count($arr);
    for ($i = 0; $i < $arrLen; $i++) {
        if (empty($bucket[$arr[$i]])) { //加1操作时需先转为0
            $bucket[$arr[$i]] = 0;
        }
        $bucket[$arr[$i]]++;
    }

    $sortedIndex = 0;
    foreach ($bucket as $key => $value) { //key为值，value为计数
        if ($value !== null){
            for($j=0;$j<(int)$value;$j++){ //不为空则循环将该值添加到数组
                $arr[$sortedIndex++] = $key;
            }
        }
    }

    return $arr;
}

var_dump(countingSort($array));

?>

函数解析

max( num/array,num) 函数

第一个参数若为数字(可为数组)则需要第二个参数，返回最大值

算法学习之路 | 计数排序[Php]

Subscribe

Comments