PHP排序算 法之基数排序(Radix Sort)实例详解
发布时间：2023-02-14 12:45:32 所属栏目：PHP教程 来源：
导读： 本篇章节讲解PHP排序算法之基数排序(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]); } } } 基数排序法是属于稳定性的排序，其时间复杂度为 好了，到这里基数排序就已经给大家介绍完了。这个算法的总结主要是通过看网上的资料，所以就不再给出原作者了。 （编辑：海洋资讯信息网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
站长推荐