基数排序

基数排序(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);