在 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); 四、计数排序的优缺点 优点： 时间复杂度低：当 k = O(n) 时，计数排序的时间复杂度为 O(n)，远优于比较排序算法的 O(n log n)。 稳定性：计数排序是一种稳定的排序算法，即相同元素的相对顺序在排序前后保持不变。 缺点： 空间复杂度高：计数排序需要额外的空间来存储计数数组和排序后的数组，空间复杂度为 O(n + k)。 适用范围有限：计数排序仅适用于整数排序，且当 k 值较大时，空间消耗会显著增加。 五、计数排序的应用场景 计数排序适用于以下场景：
数据范围较小：当数组中元素的范围 k 远小于数组长度 n 时，计数排序的效率优势明显。 需要稳定排序：当需要保持相同元素的相对顺序时，计数排序是一个不错的选择。 非负整数排序：计数排序通常用于非负整数的排序，但可以通过偏移量处理负数。 六、总结 计数排序是一种简单高效的排序算法，特别适用于数据范围较小的整数排序。在 PHP 开发中，我们可以根据实际需求选择合适的排序算法，而计数排序无疑是处理特定场景下排序问题的利器。
感谢
测试