PHP 计数排序算法
最后修改于 2025 年 4 月 16 日
基本定义
算法是一种逐步解决问题或执行计算的程序。排序算法将元素按特定顺序排列。
常见的排序算法包括冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序和计数排序。每个算法都有不同的性能特征。
计数排序概述
计数排序是一种整数排序算法，它通过计算具有不同键值的对象的数量来工作。它以 O(n + k) 时间运行，其中 n 是元素的数量，k 是输入数据的范围。
当输入数据 (k) 的范围不明显大于对象的数量 (n) 时，计数排序是有效的。它不是比较排序，在这些情况下，它可以比 O(n log n) 算法更快。
计数排序实现
以下是 PHP 中正整数的基本计数排序实现。
counting_sort.php
<?php
function countingSort(array $array): array {
$max = max($array);
$count = array_fill(0, $max + 1, 0);
foreach ($array as $num) {
$count[$num]++;
}
$sorted = [];
for ($i = 0; $i <= $max; $i++) {
while ($count[$i]-- > 0) {
$sorted[] = $i;
}
}
return $sorted;
}
$numbers = [4, 2, 2, 8, 3, 3, 1];
$sorted = countingSort($numbers);
print_r($sorted); // Outputs: [1, 2, 2, 3, 3, 4, 8]
此实现首先计算每个数字的出现次数，然后从计数中重建排序后的数组。它适用于小整数范围。
带有负数的计数排序
这是一个增强版本，通过调整索引来处理负数。
counting_sort_negative.php
<?php
function countingSort(array $array): array {
$min = min($array);
$max = max($array);
$range = $max - $min + 1;
$count = array_fill(0, $range, 0);
foreach ($array as $num) {
$count[$num - $min]++;
}
$sorted = [];
for ($i = 0; $i < $range; $i++) {
while ($count[$i]-- > 0) {
$sorted[] = $i + $min;
}
}
return $sorted;
}
$numbers = [-5, 2, -3, 8, 0, -1, 2];
$sorted = countingSort($numbers);
print_r($sorted); // Outputs: [-5, -3, -1, 0, 2, 2, 8]
该算法通过减去最小值来调整索引，使其能够处理负数，同时保持 O(n + k) 的时间复杂度。
降序计数排序
要以降序排序，我们只需反向迭代计数数组。
counting_sort_desc.php
<?php
function countingSortDesc(array $array): array {
$max = max($array);
$count = array_fill(0, $max + 1, 0);
foreach ($array as $num) {
$count[$num]++;
}
$sorted = [];
for ($i = $max; $i >= 0; $i--) {
while ($count[$i]-- > 0) {
$sorted[] = $i;
}
}
return $sorted;
}
$numbers = [4, 2, 2, 8, 3, 3, 1];
$sorted = countingSortDesc($numbers);
print_r($sorted); // Outputs: [8, 4, 3, 3, 2, 2, 1]
与升序排序的唯一区别是构建排序数组时的循环方向。这与升序版本保持相同的时间复杂度。
文本数据的计数排序
计数排序可以通过使用字符代码作为键来适应文本数据。
counting_sort_text.php
<?php
function countingSortText(string $str): string {
$chars = str_split($str);
$max = max(array_map('ord', $chars));
$min = min(array_map('ord', $chars));
$range = $max - $min + 1;
$count = array_fill(0, $range, 0);
foreach ($chars as $char) {
$count[ord($char) - $min]++;
}
$sorted = '';
for ($i = 0; $i < $range; $i++) {
while ($count[$i]-- > 0) {
$sorted .= chr($i + $min);
}
}
return $sorted;
}
$text = "counting sort";
$sorted = countingSortText($text);
echo $sorted; // Outputs: " cgiinnoorsttu"
此版本将字符转换为其 ASCII 值进行计数。请注意，它保留空格并区分大小写（大写字母排在小写字母之前）。
性能比较：计数排序与快速排序
让我们将计数排序与 PHP 内置的快速排序实现进行比较。
sort_benchmark.php
<?php
function generateRandomArray(int $size, int $min, int $max): array {
return array_map(fn() => rand($min, $max), array_fill(0, $size, 0));
}
function benchmark(callable $func, array $array): float {
$start = microtime(true);
$func($array);
return microtime(true) - $start;
}
$smallRange = generateRandomArray(10000, 0, 100);
$largeRange = generateRandomArray(10000, 0, 1000000);
$countingTimeSmall = benchmark('countingSort', $smallRange);
$quickTimeSmall = benchmark('sort', $smallRange);
$countingTimeLarge = benchmark('countingSort', $largeRange);
$quickTimeLarge = benchmark('sort', $largeRange);
echo "Small range (0-100):\n";
echo "Counting sort: " . number_format($countingTimeSmall, 6) . "s\n";
echo "Quick sort: " . number_format($quickTimeSmall, 6) . "s\n\n";
echo "Large range (0-1000000):\n";
echo "Counting sort: " . number_format($countingTimeLarge, 6) . "s\n";
echo "Quick sort: " . number_format($quickTimeLarge, 6) . "s\n";
结果会有所不同，但通常计数排序对于小范围更快，而快速排序对于大范围表现更好。计数排序的内存使用量随着范围大小的增加而增加，这使得它对于大范围不太有效。
何时使用计数排序
- 小整数范围：当 k 为 O(n) 或更小时最佳。
- 需要稳定排序：可以实现为稳定排序。
- 非比较：当比较成本很高时很有用。
- 已知范围：需要事先了解数据范围。
计数排序的局限性
- 整数数据：最适用于整数键。
- 内存使用：需要 O(k) 的额外内存。
- 大范围：对于分散的数据效率低下。
- 负数：需要进行调整才能处理。
来源
本教程通过数字和文本数据的示例介绍了 PHP 中的计数排序算法，包括与快速排序的性能比较。
作者
列出 所有 PHP 教程。