PHP 基数排序算法
最后修改于 2025 年 4 月 16 日
基本定义
算法是一种逐步解决问题或执行计算的程序。排序算法将元素按特定顺序排列。
常见的排序算法包括冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序和基数排序。 它们各自具有不同的时间和空间复杂度特征。
基数排序概述
基数排序是一种非比较型整数排序算法。 它通过从最低有效位到最高有效位对数字进行分组来处理数字。
基数排序的时间复杂度为 O(nk)，其中 n 是元素的数量，k 是最长数字中的位数。 它对于大型数据集非常有效。
数值基数排序（升序）
此示例演示了对正整数进行升序的基数排序。
numeric_radix_sort.php
<?php
function radixSort(array $arr): array {
$maxDigits = max(array_map('strlen', array_map('strval', $arr)));
for ($digit = 0; $digit < $maxDigits; $digit++) {
$buckets = array_fill(0, 10, []);
foreach ($arr as $num) {
$digitVal = (int) (($num / (10 ** $digit)) % 10);
$buckets[$digitVal][] = $num;
}
$arr = array_merge(...$buckets);
}
return $arr;
}
$numbers = [170, 45, 75, 90, 802, 24, 2, 66];
$sorted = radixSort($numbers);
print_r($sorted); // [2, 24, 45, 66, 75, 90, 170, 802]
该算法处理每个数字位，将数字分配到基于当前数字的桶中，然后按顺序收集它们。
数值基数排序（降序）
此修改后的版本通过反转桶的顺序对数字进行降序排序。
numeric_radix_sort_desc.php
<?php
function radixSortDesc(array $arr): array {
$maxDigits = max(array_map('strlen', array_map('strval', $arr)));
for ($digit = 0; $digit < $maxDigits; $digit++) {
$buckets = array_fill(0, 10, []);
foreach ($arr as $num) {
$digitVal = (int) (($num / (10 ** $digit)) % 10);
$buckets[$digitVal][] = $num;
}
$arr = array_merge(...array_reverse($buckets));
}
return $arr;
}
$numbers = [170, 45, 75, 90, 802, 24, 2, 66];
$sorted = radixSortDesc($numbers);
print_r($sorted); // [802, 170, 90, 75, 66, 45, 24, 2]
与升序排序的唯一区别是在合并之前反转桶。 这给了我们降序的结果。
字符串基数排序（升序）
基数排序也可以通过处理字符按字母顺序对字符串进行排序。
string_radix_sort.php
<?php
function stringRadixSort(array $arr): array {
$maxLength = max(array_map('strlen', $arr));
for ($pos = $maxLength - 1; $pos >= 0; $pos--) {
$buckets = array_fill(0, 256, []);
foreach ($arr as $str) {
$char = $pos < strlen($str) ? ord($str[$pos]) : 0;
$buckets[$char][] = $str;
}
$arr = array_merge(...$buckets);
}
return $arr;
}
$words = ["apple", "banana", "kiwi", "orange", "pear"];
$sorted = stringRadixSort($words);
print_r($sorted); // ["apple", "banana", "kiwi", "orange", "pear"]
这从右到左处理字符串，使用 ASCII 值进行字符比较。 较短的字符串被视为具有空字符。
字符串基数排序（降序）
对于降序字母顺序，我们反转桶的合并顺序。
string_radix_sort_desc.php
<?php
function stringRadixSortDesc(array $arr): array {
$maxLength = max(array_map('strlen', $arr));
for ($pos = $maxLength - 1; $pos >= 0; $pos--) {
$buckets = array_fill(0, 256, []);
foreach ($arr as $str) {
$char = $pos < strlen($str) ? ord($str[$pos]) : 0;
$buckets[$char][] = $str;
}
$arr = array_merge(...array_reverse($buckets));
}
return $arr;
}
$words = ["apple", "banana", "kiwi", "orange", "pear"];
$sorted = stringRadixSortDesc($words);
print_r($sorted); // ["pear", "orange", "kiwi", "banana", "apple"]
降序版本在合并之前反转桶，类似于数值降序排序实现。
基数排序与快速排序基准测试
让我们比较一下基数排序与快速排序在大型数据集上的性能。
sort_benchmark.php
<?php
function generateRandomNumbers(int $count): array {
$numbers = [];
for ($i = 0; $i < $count; $i++) {
$numbers[] = rand(1000, 999999);
}
return $numbers;
}
function benchmark(callable $sortFunc, array $data): float {
$start = microtime(true);
$sortFunc($data);
return microtime(true) - $start;
}
$largeDataset = generateRandomNumbers(100000);
$radixTime = benchmark('radixSort', $largeDataset);
$quickTime = benchmark(function($arr) { sort($arr); }, $largeDataset);
echo "Radix sort time: " . number_format($radixTime, 4) . " seconds\n";
echo "Quick sort time: " . number_format($quickTime, 4) . " seconds\n";
在包含 100,000 个数字的典型测试中，基数排序通常在整数数据上优于快速排序，尤其是在数字具有有限位数长度时。
何时使用基数排序
- 固定宽度键： 适用于排序数字或固定长度字符串
- 大型数据集： 适用于合适数据的有效 O(n) 性能
- 需要稳定排序： 保持相等元素的相对顺序
- 整数排序： 尤其适用于整数数据类型
基数排序的局限性
- 数据约束： 最好与固定大小的键一起使用
- 内存使用： 需要额外的空间用于桶
- 负数： 需要特殊处理带符号的整数
- 浮点数： 不直接适用于浮点数
来源
本教程介绍了 PHP 中的基数排序算法，并提供了数值和文本数据升序和降序排序的示例。
作者
列出 所有 PHP 教程。