基数排序的思想是，输入数据的排序是从最低有效位到最高有效位逐位进行的，它使用计数排序作为子例程来执行排序。计数排序是一种线性排序算法，在所有情况下总时间复杂度为 θ(N+K)，其中 N 是未排序数组中的元素数量， K是输入数据的范围。基数排序的思想是扩展计数排序算法，以便在K上升时获得更好的时间复杂度。
示例:
理解基数排序，让我们考虑一个未排序的数组 A = [101, 1, 20, 50, 9, 98, 27, 153, 35, 899] 并讨论按升序对数组进行排序所采取的每个步骤。
第1步:根据算法，输入数据首先根据最低有效位进行排序。因此，数组A[]是根据数字排序的。按数字排序后，将变为[20, 50, 101, 1, 153, 35, 27, 98, 9, 899]。
第 2 步:在这一步中，数组 A[ ] 数组按照十位进行排序，经过这一步后，它将变成 [101, 1, 9, 20, 27, 35, 50, 153, 98, 899]。
第 3 步:最后，数组 A[ ] 根据百位（最高有效位）排序，数组将在此步骤之后进行排序，最终数组将为[1, 9, 20, 27, 35, 50, 98, 101, 153, 899]。
基数排序的实现
<?php
// 基数排序函数
function radixsort(&$Array, $n) {
$max = $Array[0];
//查找数组中最大的元素
for ($i=1; $i<$n; $i++) {
if($max < $Array[$i])
$max = $Array[$i];
}
//按照地点进行计数排序。
//比如个位、十位等等。
for ($place = 1; $max/$place > 0; $place *= 10)
countingsort($Array, $n, $place);
}
function countingsort(&$Array, $n, $place) {
$output = array_fill(0,$n,0);
//对于每个考虑的地方，数字的范围是0-9。
$freq = array_fill(0,10,0);
//计算freq数组中出现的次数
for($i = 0; $i < $n; $i++)
$freq[($Array[$i]/$place)%10]++;
//更改 count[i] 以便 count[i] 现在包含实际的
//该数字在输出[]中的位置
for ($i = 1; $i < 10; $i++)
$freq[$i] += $freq[$i - 1];
//构建输出数组
for ($i = $n - 1; $i >= 0; $i--) {
$output[$freq[($Array[$i]/$place)%10] - 1] = $Array[$i];
$freq[($Array[$i]/$place)%10]--;
}
//将输出数组复制到输入数组，现在数组将
//包含基于指定位置的数字排序的数组
for ($i = 0; $i < $n; $i++)
$Array[$i] = $output[$i];
}
//打印数组的函数
function PrintArray($Array, $n) {
for ($i = 0; $i < $n; $i++)
echo $Array[$i]." ";
echo "\n";
}
//测试代码
$MyArray = array(101, 1, 20, 50, 9, 98, 27, 153, 35, 899);
$n = sizeof($MyArray);
echo "原始数组\n";
PrintArray($MyArray, $n);
radixsort($MyArray, $n);
echo "\n排序数组\n";
PrintArray($MyArray, $n);
?> 上述代码将给出以下输出:
原始数组
101 1 20 50 9 98 27 153 35 899
排序数组
1 9 20 27 35 50 98 101 153 899 时间复杂度:
基数排序的时间复杂度为θ((N+b)*log b(max)) 在所有情况下，其中:
- N 是未排序数组中的元素数量。
- b 是输入数组的基数，例如，对于十进制系统，b 为 10。
- max 是输入数组的最大元素。