在《基数排序（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);

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