10大经典排序算法之基数排序(PHP版)

发布时间:2020/11/23 作者:天马行空 阅读(180)

基数排序,是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。


算法步骤
1、取出数组中最大值,算出来有多少位
2、从个位开始取余数,根据余数将数据放入0-9的桶中
3、将桶中的数据取出来填充到原来的数组中
4、重复2、3步骤对十位、百位...取余、装桶、回填,完成排序


动图演示

radixSort.gif


代码实现:

function radixSort(array $arr)
{
    $arr_len = count($arr);
    
    if ($arr_len <= 1) {
        return $arr;
    }
    
    $max = max($arr); // 用Math的max函数获取数组中的最大值
    
    $max_len = strlen($max); // 获取最大的数的位数
    
    $radix = 1; // 基数,从最后一位数开始
    for ($i = 0; $i < $max_len; $i ++) { // 按最大位数读取各位的数
        for ($j = 0; $j < 10; $j ++) {
            $buckets[$j] = []; // 用来装不同基数对应的值
        }
        
        foreach ($arr as $val) { // 按基数把数放到桶里
            $buckets[($val / $radix) % 10][] = $val;
        }
        
        $radix *= 10; // 基数进位
        
        $k = 0;
        $arr = [];
        foreach ($buckets as $bucket) { // 把桶里的数重新存起来
            foreach ($bucket as $val) {
                $arr[$k ++] = $val;
            }
        }
    }
    
    return $arr;
}



关键字php 算法