数据结构与算法(php版)排序之基数排序(MSD)

yang-pig| 阅读:395 发表时间:2018-07-25 23:43:27 算法

在上一篇文章中,我们对基数排序的概念和效率分析进行了讲解。在这篇文章中我们不再加以赘述。大家可以参考那篇文章,对基数排序的思想进行大概的了解。

下面我们直接来介绍MSD基数排序的步骤。

MSD基数排序是从最高位开始对序列进行分组,到最低位为止。但是其实现过程是和LSD基数排序不同的,排序过程中需要用到递归函数。

待排序序列

170, 45, 75, 90, 2, 24, 802, 66

我们看到,这里面的最大的数是3位数。所以说我们开始从百位对这些数进行分组

0: 045, 075, 090,002, 024, 0661: 1702-7: 空8: 8029: 空

从这里开始就和LSD基数排序有差别了。在LSD基数排序中,每次分好组以后开始对桶中的数据进行收集。然后根据下一位,对收集后的序列进行分组。而对于MSD,在这里不会对桶中的数据进行收集。我们要做的是检测每个桶中的数据。当桶中的元素个数多于1个的时候,要对这个桶递归进行下一位的分组。

在这个例子中,我们要对0桶中的所有元素根据十位上的数字进行分组

0: 0021: 空2: 0243: 空4: 0455: 空6: 0667: 0758: 空9: 090

按照上面所说,我们应该再递归的对每个桶中的元素根据个位上的数进行分组。但是我们发现,现在在每个桶中的元素的个数都是小于等于1的。因此,到这一步我们就开始回退了。也就是说我们开始收集桶中的数据。收集完成以后,回退到上一层。此时按照百位进行分组的桶变成了如下的形式

0: 002, 024, 045,066, 075, 0901: 1702-7: 空8: 8029: 空

然后我们在对这个桶中的数据进行收集。收集起来以后序列如下

2, 24, 45, 66, 75, 90, 170, 802

整个MSD基数排序就是按照上面的过程进行的。

在我对MSD基数排序步骤进行叙述的时候,中间递归函数的过程可能叙述的不够清楚。我个人建议对递归函数不了解的可以先了解一下递归函数的原理,然后再回来看这个过程可能对MSD基数排序过程更容易理解。

当然,一个排序算法需要有代码的实现。下面我为大家奉上MSD基数排序的PHP代码


<?php
/**
 * 基数排序(MSD)
 * 分析:MSD基数排序是从最高位开始对序列进行分组,到最低位为止。
 * 但是其实现过程是和LSD基数排序不同的,排序过程中需要用到递归函数。
 * 参考:https://www.onmpw.com/tm/xwzj/algorithm_117.html
 *
 */

/**
 * 找到序列中最大位数
 * @param $arr
 * @return int
 */
function FindMaxBit($arr){
    /*
     * 首先查找序列中最大的数
     */
    $p = $arr[0];
    for($i=1;$i<count($arr);$i++){
        if($arr[$i]>=$p){
            $p = $arr[$i];
        }
    }
    //得到最大的数以后,计算出该数据有多少位
    $d = 1;
    while(floor($p/10)>0){
        $d++;
        $p = floor($p/10);
    }
    return $d;
}
/**
 * MSD基数排序函数
 * @param array $arr  待分组的序列
 * @param int $r    表示当前是按照第几位进行分组
 * @return array
 */
function MSD_RadixSort(&$arr,$r){
    $radix = pow(10,$r-1);

    $bucket = array();
    //初始化队列
    for($i=0;$i<10;$i++){
        $bucket[$i]=array('num'=>0,'val'=>array());
    }
    for($j=0;$j<count($arr);$j++){
        $k = floor($arr[$j]/$radix)%10;

        $bucket[$k]['num']++;
        array_push($bucket[$k]['val'],$arr[$j]);
    }

    for($j=0;$j<10;$j++){
        if($bucket[$j]['num']>1){
            MSD_RadixSort($bucket[$j]['val'],$r-1);
        }
    }

    /*
     * 将桶中的数据收集起来,此时序列是有序的
     */
    $arr = array();
    for($j=0;$j<10;$j++){
        for($i=0;$i<count($bucket[$j]['val']);$i++){
            $arr[] = $bucket[$j]['val'][$i];
        }
    }
    return $arr;
}

$arr = array(
    15,77,23,43,90,87,68,32,11,22,33,99,88,66,44,113,
    224,765,980,159,456,7,998,451,96,0,673,82,91,100
);

var_dump(MSD_RadixSort($arr,3));

1.png

5.png

2.png

3.png

4.png