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

Posted ·678 Views·774 Words

思路

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

 

代码

<?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) 函数

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

Comments

Leave a comment to join the discussion