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

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

一、计数排序简介

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

二、计数排序的步骤

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

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

三、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 开发中，我们可以根据实际需求选择合适的排序算法，而计数排序无疑是处理特定场景下排序问题的利器。