排序算法学习之路——基数排序（msd）-ag捕鱼王app官网

当前位置：ag捕鱼王app官网 > > 算法 >

web前端编程语言网络算法操作系统数据库

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

作者：迹忆最近更新：2022/11/19 浏览次数：

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

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

上一篇：排序算法学习之路——基数排序（lsd）

下一篇：php查找多个字符串的公共前缀【案例】

转载请发邮件至 1244347461@qq.com 进行申请，经作者同意之后，转载请以链接形式注明出处

本文地址：

发布时间：2023/10/17 浏览次数：153 分类：java

本教程演示了 java 中的选择排序算法。选择排序是首先选择列表或数组中最小的元素并与第一个元素或数组交换的方法；然后，第二个缩小的元素与第二个元素交换。

java 基数排序算法

发布时间：2023/10/17 浏览次数：206 分类：java

本教程详细解释了基数排序算法并演示了 java 中的实现。在基数排序算法中，元素的排序首先将具有相同位值的单个数字分组，然后按照升序或降序排序。本教程详细解释了基数排序算法，并演

发布时间：2023/10/11 浏览次数：110 分类：java

首先，我们将通过节点示例讨论 java 中的冒泡排序算法。然后，我们将执行两种方法来演示如何使用手动冒泡排序算法对链表进行排序。

发布时间：2023/08/31 浏览次数：164 分类：c

本文将解释哪种排序算法在什么条件下表现最好。条件包括数据结构的类型、排序数据的大小、数据排列和数据元素的范围。

java最快的排序算法

发布时间：2023/07/16 浏览次数：164 分类：java

本文将介绍两种最快的排序算法并用 java 编写它们的代码。第一种技术是计数排序，它有一些局限性。因此，我们还将介绍合并排序算法。 java中的计数排序算法 java中的归并排序算法

发布时间：2021/08/19 浏览次数：323 分类：算法

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（divide and conquer）的一个非常典型的应用。这里拆分过程的代码可以分为两种方式：递归实现和非递归实现

排序算法学习之路——基数排序（msd）-ag捕鱼王app官网