计数排序是一种非比较型整数排序算法，时间复杂度O(n+k)，要求元素为非负整数（负数需偏移），空间复杂度O(k)，适用于值域不大的整数排序。
计数排序（Counting Sort）是一种非比较型整数排序算法，适用于一定范围内的整数排序，时间复杂度为 O(n + k)，其中 k 是数据的值域大小。它不基于元素间的比较，而是利用数组下标作为键，统计每个元素出现的频次，再按顺序还原出有序序列。
适用前提与限制
计数排序要求待排序元素必须是**非负整数**，且最大值不能过大（否则辅助数组会占用过多内存）。若含负数，可整体偏移；若为小数或字符串，则不适用，应换用其他排序算法。
- 输入必须是整数数组，如 [4, 2, 2, 8, 3, 3, 1]
- 需预先知道最小值和最大值，或遍历一次获取 min 和 max
- 空间复杂度为 O(k)，k = max - min + 1，需权衡内存使用
PHP实现步骤详解
核心思路：统计频次 → 计算前缀和（可选，用于稳定排序）→ 从后往前填入输出数组（保证稳定性）。
- 第一步：遍历原数组，用 $count[$num] 记录每个数出现次数
- 第二步：找出最小值 $min 和最大值 $max，初始化长度为 $max - $min + 1 的计数数组
- 第三步：将原数组每个元素除以偏移量（即减去 $min），存入对应下标位置
- 第四步：遍历计数数组，按频次依次输出 $i + $min，重复 $count[$i] 次
完整可运行代码示例
以下是一个支持含负数的健壮版计数排序函数：
立即学习“PHP免费学习笔记（深入）”；
function countingSort(array $arr): array
{
if (empty($arr)) return $arr;
<pre class="brush:php;toolbar:false;">$min = min($arr);
$max = max($arr);
$range = $max - $min + 1;
$count = array_fill(0, $range, 0);
// 统计频次（统一偏移）
foreach ($arr as $num) {
$count[$num - $min]++;
}
// 重建有序数组
$sorted = [];
for ($i = 0; $i < $range; $i++) {
while ($count[$i] > 0) {
$sorted[] = $i + $min;
$count[$i]--;
}
}
return $sorted;}
// 测试 $nums = [4, 2, -1, 2, 8, 3, -1, 1]; print_r(countingSort($nums)); // 输出：[-1, -1, 1, 2, 2, 3, 4, 8]
优化与注意事项
实际项目中需注意边界与性能取舍：
- 若值域极大（如上亿）、但数据稀疏，改用桶排序或哈希映射更合适
- PHP 中用 array_fill 初始化计数数组比循环赋值更高效
- 避免直接用 $num 作下标（如 $count[$num]++），以防负数导致 PHP 警告或逻辑错误
- 该实现是稳定排序；若只求结果正确、不强调稳定性，内层 while 可替换为 array_fill + array_merge
