JIYIK CN >

In the article "Radix Sort (LSD)" , we explained the concept and efficiency analysis of radix sort. We will not repeat it in this article. You can refer to that article to get a general understanding of the idea of ​​radix sort.

Next, we will directly introduce the steps of MSD radix sort.

MSD radix sorting groups the sequence from the highest digit to the lowest digit. However, its implementation is different from LSD radix sorting, and a recursive function is required in the sorting process.

Sequence to be sorted

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

We can see that the largest number here is a 3-digit number. So we start to group these numbers from the hundreds place

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

From here on, it is different from LSD radix sort. In LSD radix sort, after each grouping, the data in the bucket is collected. Then the collected sequence is grouped according to the next bit. For MSD, the data in the bucket is not collected here. What we need to do is to check the data in each bucket. When the number of elements in the bucket is more than 1, the bucket should be recursively grouped for the next bit.

In this example, we want to group all the elements in bucket 0 according to the digits in the tens place.

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

According to what is said above, we should recursively group the elements in each bucket according to the number in the ones place. However, we find that the number of elements in each bucket is less than or equal to 1. Therefore, we start to back off at this step. In other words, we start to collect the data in the bucket. After the collection is completed, we back off to the previous level. At this time, the buckets grouped according to the hundreds place become as follows

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

Then we collect the data in this bucket. After collection, the sequence is as follows

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

The entire MSD cardinality sorting is performed according to the above process.

When I described the steps of MSD radix sorting, the process of the intermediate recursive function may not be described clearly enough. I personally suggest that those who don’t understand recursive functions can first understand the principle of recursive functions, and then come back to this process, which may make it easier to understand the MSD radix sorting process.

Of course, a sorting algorithm needs to be implemented in code. Here is the PHP code for MSD radix sorting.

/**
 * 找到序列中最大位数
 */
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);

I hope this article is helpful to you.