基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法
方法:最高位优先MSD、最低位优先LSD
思想:最低位优先LSD方案
1、 将待排数字根据个位上的数字进行排序
2、 将待第一步排序结果再按照十位上数字进行排序
3、 按照位数从低到高依次排序
示例:
$arr = array(1,4,5,89,22,44,5,33,6,7,82,332);
function getIndex($num, $index) {
$val = pow(10, $index - 1);
return ($num / $val) % 10;
}
function radix_sort($arr,$max_len) {
for($i = 1; $i <= $max_len; $i++) {
$temp = array_fill(0, 10, array());//填充桶
foreach ($arr as $v) {
echo $index = getIndex($v, $i);
echo '#';
$temp[$index][] = $v;
}
$arr = array();
echo "\n第".$i. '次排序之后:';
foreach ($temp as $v) {
for($j =0 ;$j < count($v); $j++) {
echo $v[$j] ."," ;
$arr[] = $v[$j];
}
}
echo "\n";
}
return $arr;
}
$arr = radix_sort($arr, 3);
print_r($arr);
以上示例有一个问题,如果排序的数字是负数呢?
$arr = array(1,4,5,89,22,44,-5,33,-6,7,-82,332);
function getIndex($num, $index) {
$val = pow(10, $index - 1);
return 10+($num / $val) % 10;
}
function radix_sort($arr,$max_len) {
for($i = 1; $i <= $max_len; $i++) {
$temp = array_fill(0, 19, array());//填充桶,负数填充-9~0~9对应0~10~19
foreach ($arr as $v) {
echo $index = getIndex($v, $i);
echo '#';
$temp[$index][] = $v;
}
$arr = array();
echo "\n第".$i. '次排序之后:';
foreach ($temp as $v) {
for($j =0 ;$j < count($v); $j++) {
echo $v[$j] ."," ;
$arr[] = $v[$j];
}
}
echo "\n";
}
return $arr;
}
$arr = radix_sort($arr, 3);
print_r($arr);