排序算法学习之路——基数排序（MSD）

Z时代
2024-01-10
分类：综合

在《基数排序（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代码

/**
 * 找到序列中最大位数
 */
functionFindMaxBit($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    表示当前是按照第几位进行分组
 */
functionMSD_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);