迹忆客 专注技术分享

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

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

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

待排序序列

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

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

0: 045, 075, 090,002, 024, 066
1: 170
2-7: 空
8: 802
9: 空

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

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

0: 002
1: 空
2: 024
3: 空
4: 045
5: 空
6: 066
7: 075
8: 空
9: 090

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

0: 002, 024, 045,066, 075, 090
1: 170
2-7: 空
8: 802
9: 空

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

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

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

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

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

/**
 * 找到序列中最大位数
 */
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 array $r    表示当前是按照第几位进行分组
 */
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]%pow(10,$r)/$radix);
        $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];
        }
    }
}
$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
);
MSD_RadixSort($arr,FindMaxBit($arr));
print_r($arr);

希望本文对大家有所帮助。