PHP百题练习：PHP怎么实现基数排序算法-php教程-PHP中文网

基数排序是不比较元素大小、按位多次计数排序的稳定非比较型算法，适用于位数少、数据量大的非负整数；需先求最大位数，再从个位起逐位用计数排序处理，时间复杂度o(d×(n+10))，空间复杂度o(n)。

php百题练习：php怎么实现基数排序算法

PHP 实现基数排序（Radix Sort）的关键在于：它不直接比较元素大小，而是按数字的每一位（个位、十位、百位……）进行多次计数排序（Counting Sort），属于一种稳定的非比较型整数排序算法。适合处理位数不多但数据量较大的正整数序列。

基数排序的核心思路

基数排序从最低有效位（LSD，Least Significant Digit）开始，对每一位执行一次稳定排序（通常用计数排序），逐步“累积”出整体有序结果。每轮排序后，相同位值的元素相对顺序不变，这是稳定性的体现，也是保证最终正确性的前提。

只适用于非负整数（如需支持负数或浮点数，需额外预处理）
需要知道最大数的位数，或动态计算位数
每轮排序依赖稳定的子排序（PHP 中用计数排序最自然）

PHP 实现步骤详解

以十进制为例，按个→十→百…顺序处理每位数字：

btpanel phpsite 宝塔面板PHP网站

宝塔面板 PHP 网站管理：站点创建、删除、启停、PHP 版本切换、域名管理、SSL证书管理、伪静态管理、数据库管理

下载

求最大位数：遍历数组找最大值，用 floor(log10($max)) + 1 或字符串转换（strlen((string)$max)）获取总位数
逐位计数排序：对第 $digit 位（从 0 开始，0 表示个位），提取该位数字：($num / pow(10, $digit)) % 10，转为整数
构建桶数组：用长度为 10 的数组 $count[0..9] 统计每位数字出现频次，再转为前缀和（位置索引），最后倒序遍历原数组完成分配
覆盖原数组：每轮排序后将临时结果写回原数组，为下一轮准备

完整可运行代码示例

以下是一个简洁、无扩展依赖的标准实现（支持 0~99999 范围内正整数）：

function radixSort(array $arr): array
{
    if (count($arr) // 找最大值，确定位数
$max = max($arr);
$digits = $max > 0 ? floor(log10($max)) + 1 : 1;

// 拷贝数组避免修改原数组
$output = $arr;

// 对每一位进行计数排序（LSD）
for ($d = 0; $d = 0; $i--) {
        $digitVal = ($output[$i] / $exp) % 10;
        $pos = $count[(int)$digitVal] - 1;
        $temp[$pos] = $output[$i];
        $count[(int)$digitVal]--;
    }

    $output = $temp;
}

return $output;

}

// 测试 $nums = [170, 45, 75, 90, 2, 802, 24, 66]; print_r(radixSort($nums)); // 输出：[2, 24, 45, 66, 75, 90, 170, 802]