PHP – 计数排序 – 老迟笔记

一、概述

计数排序（Counting sort）是一种稳定的排序算法。计数排序需要使用一个额外的数组countArray，其中第 i 个元素是待排序数组 array 中值等于 i 的元素个数。然后根据数组countArray将 array 中的元素排到正确的位置。

注意：他只能对整数进行排序。

1、计数排序的算法原理

（1）找出待排序的数组中最大元素和最小元素

（2）统计数组中的每个值为 i 的元素出现的次数，存入数组 countArray 的第 i 项，countArray[i] 表示数组中等于 i 的元素出现的次数。

（3）从待排序列 array 的第一个元素开始，将 array[i] 放到正确的位置，即前面有几个元素小于等于它，他就放在第几个位置。

二、PHP 代码实现

<?php
declare(strict_types = 1);
class TestCase
{
    /**
     * 计数排序
     *
     * @param array $array
     * @return array
     */
    public function sortArray(array $array) : array
    {
        $arrayLen = count($array);
        if ($arrayLen <= 1) {
            return $array;
        }
        $min = min($array);
        $max = max($array);
        $countArray = [];

        // 构造计数数组，键为待排序数组的值, 构造的计数数组的键的范围从数组最小值到最大值
        for ($i = $min; $i <= $max; $i++) {
            $countArray[$i] = 0;
        }

        // 开始计数
        foreach ($array as $v) {
            $countArray[$v]++;
        }

        $finalArray = [];
        foreach ($countArray as $index => $value) {
            for ($i = 0; $i < $value; $i++) {
                $finalArray[] = $index;
            }
        }
        return $finalArray;
    }
}

// 需要排序数组
$arr = [20, 19, 15, 36, 22, 3, 77, 95, 64, 17, 24, 36];
$arrObject = new TestCase();
// 执行排序
$arr = $arrObject->sortArray($arr);
// 输出结果
foreach ($arr as $v) {
    echo $v . ' ';
}

三、算法性能分析

当输入的元素个数是 n 个 0 ~ k 之间的整数时，它的运行时间是 O(n + k)。

计数排序不是比较排序，所以排序的速度快于任何比较排序算法。

最好情况：T(n) = O(n + k)

最差情况：T(n) = O(n + k)

平均情况：T(n) = O(n + k)

打赏赞