你还在用冒泡排序？PHP 计数排序了解一下！

云游道人 2025-04-11 457 阅读 0评论

在 PHP 开发中，排序算法是处理数据时不可或缺的工具。面对海量数据，选择高效的排序算法至关重要。本文将介绍一种简单却高效的排序算法——计数排序，并探讨其在 PHP 中的实现和应用场景。

一、计数排序简介

计数排序是一种非比较型整数排序算法，其核心思想是通过统计数组中每个元素出现的次数，进而确定元素在排序后数组中的位置。与常见的比较排序算法（如快速排序、归并排序）相比，计数排序的优势在于其时间复杂度仅为 O(n + k)，其中 n 是数组长度，k 是数组中最大元素与最小元素的差值。这使得计数排序在处理一定范围内的整数排序时，效率极高。

二、计数排序的步骤

计数排序的实现步骤如下：

找出数组中的最大值和最小值：确定数组中元素的范围。
统计每个元素出现的次数：创建一个计数数组，用于记录每个元素出现的次数。
累加计数数组：将计数数组中的元素进行累加，得到每个元素在排序后数组中的最后一个位置。
反向填充目标数组：遍历原数组，根据计数数组中的信息，将元素放置到目标数组的相应位置。

三、PHP 实现计数排序

以下是一个用 PHP 实现计数排序的示例代码：

function countingSort(array $arr): array {
    $max = max($arr);
    $min = min($arr);
    $range = $max - $min + 1;

    // 初始化计数数组
    $count = array_fill(0, $range, 0);

    // 统计每个元素出现的次数
    foreach ($arr as $num) {
        $count[$num - $min]++;
    }

    // 累加计数数组
    for ($i = 1; $i < $range; $i++) {
        $count[$i] += $count[$i - 1];
    }

    // 反向填充目标数组
    $sortedArr = array_fill(0, count($arr), 0);
    for ($i = count($arr) - 1; $i >= 0; $i--) {
        $sortedArr[--$count[$arr[$i] - $min]] = $arr[$i];
    }

    return $sortedArr;
}

// 示例
$arr = [5, 3, 1, 2, 4, 5, 2];
$sortedArr = countingSort($arr);
print_r($sortedArr);