php 实现基数排序

1、基数排序介绍

基数排序是一种基于数字每一位进行排序的算法。它从最低位开始，依次对每一位进行排序，直到最高位。对于整数，从个位开始，将所有数字按照个位数字放入相应的“桶”中，然后按桶的顺序重新收集数据；接着对十位进行同样的操作，以此类推，直到处理完最高位。例如，对于数组[123, 456, 789, 111, 222]，先按个位数字排序，再按十位数字排序，最后按百位数字排序，从而得到有序数组。

2、PHP代码实现（支持处理负数）：

function radixSort($arr) {
    $n = count($arr);
    if ($n <= 1) return $arr;

    // 处理负数：转换为非负整数
    $minVal = min($arr);
    $offset = ($minVal < 0) ? -$minVal : 0;
    foreach ($arr as &$num) {
        $num += $offset;
    }

    // 获取最大值确定位数
    $maxVal = max($arr);
    $exp = 1; // 从个位开始

    while (floor($maxVal / $exp) > 0) {
        $arr = countingSort($arr, $exp);
        $exp *= 10; // 处理十位、百位...
    }

    // 恢复原始数值（减去偏移量）
    if ($offset != 0) {
        foreach ($arr as &$num) {
            $num -= $offset;
        }
    }

    return $arr;
}

function countingSort($arr, $exp) {
    $n = count($arr);
    $output = array_fill(0, $n, 0);
    $count = array_fill(0, 10, 0);

    // 统计当前位的出现次数
    foreach ($arr as $num) {
        $digit = floor(($num / $exp) % 10);
        $count[$digit]++;
    }

    // 计算累加位置
    for ($i = 1; $i < 10; $i++) {
        $count[$i] += $count[$i - 1];
    }

    // 反向填充保证稳定性
    for ($i = $n - 1; $i >= 0; $i--) {
        $digit = floor(($arr[$i] / $exp) % 10);
        $output[$count[$digit] - 1] = $arr[$i];
        $count[$digit]--;
    }

    return $output;
}

// 示例测试
$testCases = [
    [-5, 10, -3, 2, 0],   // 含负数
    [170, 45, 75, 90, 802, 24, 2, 66],
    [0, 0, 1, 1, 0],      // 重复元素
    [10000, 999, 100, 10, 1],
];

foreach ($testCases as $nums) {
    $sorted = radixSort($nums);
    echo "排序前: " . implode(", ", $nums) . "\n";
    echo "排序后: " . implode(", ", $sorted) . "\n\n";
}

3、执行结果示例

排序前: -5, 10, -3, 2, 0
排序后: -5, -3, 0, 2, 10

排序前: 170, 45, 75, 90, 802, 24, 2, 66
排序后: 2, 24, 45, 66, 75, 90, 170, 802

排序前: 0, 0, 1, 1, 0
排序后: 0, 0, 0, 1, 1

排序前: 10000, 999, 100, 10, 1
排序后: 1, 10, 100, 999, 10000

4、代码解释

1. 处理负数

• 找到最小值 $minVal，计算偏移量 $offset。
• 将所有元素加上 $offset，确保数组中的值非负。

2. 按位排序（核心逻辑）

• 确定最大位数：根据 $maxVal 计算需要处理的位数，例如 802 需要处理到百位（exp=100）。
• 计数排序：对当前位（个位、十位、百位等）进行稳定排序：
  • 统计频率：统计每个数字（0-9）出现的次数。
  • 计算累加位置：将 $count 数组转换为每个数字的结束索引。
  • 反向填充：从原数组末尾遍历，按当前位数字放入 $output 数组的正确位置。

3. 恢复原始值

• 排序完成后，如果存在负数，将每个元素减去 $offset，恢复原始数值。

5、复杂度分析

• 时间复杂度：O(d*(n + k))，其中：
  • d 是最大位数，k 是基数（十进制为10）。
  • 每个位数需要进行一次计数排序（O(n + k)）。
• 空间复杂度：O(n + k)，用于计数数组 $count 和输出数组 $output。

6、适用场景

• 整数或定长字符串排序：如手机号、身份证号的排序。
• 数据范围大但位数少：例如对 10^6 个 3 位数排序。
• 需要稳定排序：如对多关键字排序（先按第二位排序，再按第一位）。