站长网 PHP教程 PHP排序算法之基数排序(Radix Sort)实例详解

PHP排序算法之基数排序(Radix Sort)实例详解

本篇章节讲解PHP排序算法之基数排序(Radix Sort)。分享给大家供大家参考,具体如下: 基数排序在《》中并未讲到,但是为了凑齐八大排序算法,我自己通过网络学习了这个排序算法,并给大家分享出来。 基本思想: 基数排序(radix sort)属于“分配式排序”

本篇章节讲解PHP排序算法之基数排序(Radix Sort)。分享给大家供大家参考,具体如下:

基数排序在《》中并未讲到,但是为了凑齐八大排序算法,我自己通过网络学习了这个排序算法,并给大家分享出来。

基本思想:

基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。

其实这个思想我也没法总结出来,下面通过例子来说明吧:

基本解法:

PS:在这里我们介绍的基数排序我们采用 LSD(最低位优先),当然还有 MSD(最高位优先),大家自己去百度一下他们之间的异同吧。

假如现在我们有以下这么一些数:

我们使用基数排序将他们从小到大排序。

第一步、首先根据个位数的数值,在走访数值(从前到后走访,后面步骤相同)时将它们分配至编号0到9的桶子中:

第二步、接下来将这些桶子中的数值重新串接起来,成为以下的数列:

第三步、根据十位数的数值,在走访数值(从前到后走访,后面步骤相同)时将它们分配至编号0到9的桶子中:

第四步、接下来将这些桶子中的数值重新串接起来,成为以下的数列:

第五步、根据百位数的数值,在走访数值(从前到后走访,后面步骤相同)时将它们分配至编号0到9的桶子中:

第六步、接下来将这些桶子中的数值重新串接起来,成为以下的数列:

。。。。。。后面的步骤大家应该都会走了吧。其实到了第六步的时候就剩 4249 没有排好序了。

从上面的步骤来看,很多的步骤都是相同的,因此肯定是个循环了,我们只需要控制个位、十位、百位、、、、就好了。

还是看代码吧。

算法实现:

调用算法:

运行结果:

int(1)
[1]=>
int(2)
[2]=>
int(3)
[3]=>
int(43)
[4]=>
int(128)
[5]=>
int(342)
[6]=>
int(343)
[7]=>
int(654)
[8]=>
int(687)
[9]=>
int(814)
[10]=>
int(4249)
}

其实这些代码我是在挺早之前写的,今天在写博客的时候发现,其实桶就是一个队列,所以上面的 R_Sort()函数复杂了,我们使用 array_push() array_shift() 来重写该方法(当然,要模拟队列的话,用 SPL 提供的 splqueue 是最为恰当的,在这里为了简便我就不用了):

0){
$arr[$k ++] = array_shift($tempArr[$i]);
}
}
}

基数排序法是属于稳定性的排序,其时间复杂度为

好了,到这里基数排序就已经给大家介绍完了。这个算法的总结主要是通过看网上的资料,所以就不再给出原作者了。

PS:这里再为大家推荐一款关于排序的演示工具供大家参考:

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具:

更多关于PHP相关内容感兴趣的读者可查看本站专题:《》、《》、《》、《》、《》、《》及《》

希望本文所述对大家PHP程序设计有所帮助。

本文来自网络,不代表站长网立场,转载请注明出处:https://www.zwzz.com.cn/html/jc/php/2021/0523/4748.html

作者: dawei

【声明】:站长网内容转载自互联网,其相关言论仅代表作者个人观点绝非权威,不代表本站立场。如您发现内容存在版权问题,请提交相关链接至邮箱:bqsm@foxmail.com,我们将及时予以处理。
联系我们

联系我们

0577-28828765

在线咨询: QQ交谈

邮箱: xwei067@foxmail.com

工作时间:周一至周五,9:00-17:30,节假日休息

返回顶部