计数排序 - Counting Sort

简介

计数排序是一种稳定的线性时间排序算法。
计数排序使用一个额外的数组 C，其中第i个元素是待排序数组 A 中值等于i 的元素的个数。然后根据数组 C 来将 A 中的元素排到正确的位置。

时间复杂度

当输入的元素是 n 个 0 到 k 之间的整数时，时间复杂度为 O ( n + k )

代码

方法一

public function counting_sort()
{
    $arr = [0, 3, 6, 2, 4, 10, 2, 4, 78];

    $min = min($arr);  // 数组最小值
    $max = max($arr);  // 数组最大值

    // 循环数组，计算每个元素出现的次数，$count[] 下标为 $arr 元素值
    $count = [];
    foreach ($arr as $k) {
        $count[$k] = isset($count[$k]) ? $count[$k]+1 : 1;
    }

    // 从最小值循环到最大值，如果在 $arr 有出现，则按出现的次数插入 $sort 中
    $sort = [];
    for ($i=$min; $i<=$max; $i++) {
        if (isset($count[$i])) {
            // 循环个数，插入
            while ($count[$i]-- > 0) {
                $sort[] =$i;
            }
        }
    }
}

方法二

public function counting_sort()
{
    $arr   = [0, 3, 6, 2, 4, 10, 2, 4, 78];

    //SplFixedArray 具有固定长度，并且仅允许范围内的整数作为索引。
    $count = new \SplFixedArray(max($arr)+1);

    // 统计数字个数： 循环数组$arr，将其值作为 $count数组的下标，下标对应的值为数字的个数
    foreach ($arr as $k) {
        $count[$k] =  $count[$k] + 1 ;
    }

    // 填充到目标数组 $sort：根据统计的数量，push 到新数组 $sort
    $sort = [];
    foreach ($count as $item => $i) {
        // 如果统计数组 $count 的值不为 null
        if (!empty($i)) {
            // 循环个数，插入
           while ($i-- > 0) {
               $sort[] = $item;
           }
        }
    }
}

打印 $sort

笔记

SplFixedArray 类：生成固定长度数组

本作品采用《CC 协议》，转载必须注明作者和本文链接