• 售前

  • 售后

热门帖子
入门百科

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

[复制链接]
穆一平 显示全部楼层 发表于 2021-10-25 19:37:20 |阅读模式 打印 上一主题 下一主题
本文实例讲述了PHP排序算法之基数排序(Radix Sort)。分享给各人供各人参考,详细如下:
基数排序在《大话数据结构》中并未讲到,但是为了凑齐八大排序算法,我本身通过网络学习了这个排序算法,并给各人分享出来。
根本头脑:
基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以到达排序的作用,基数排序法是属于稳固性的排序,当时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于别的的稳固性排序法。
其实这个头脑我也没法总结出来,下面通过例子来说明吧:
根本解法:
PS:在这里我们介绍的基数排序我们接纳 LSD(最低位优先),当然另有 MSD(最高位优先),各人本身去百度一下他们之间的异同吧。
如果如今我们有以下这么一些数:
2 343 342 1 128 43 4249 814 687 654 3
我们使用基数排序将他们从小到大排序。
第一步、首先根据个位数的数值,在走访数值(从前到后走访,反面步骤相同)时将它们分配至编号0到9的桶子中:
0 :
1 : 1
2 : 2 342
3 : 343 43 3
4 : 814 654
5 :
6 :
7 : 687
8 : 128
9 : 4249

第二步、接下来将这些桶子中的数值重新串接起来,成为以下的数列:
1 2 342 343 43 3 814 654 687 128 4249
第三步、根据十位数的数值,在走访数值(从前到后走访,反面步骤相同)时将它们分配至编号0到9的桶子中:
0 : 1 2 3
1 : 814
2 : 128
3 :
4 : 342 343 43 4249
5 : 654
6 :
7 :
8 : 687
9 :

第四步、接下来将这些桶子中的数值重新串接起来,成为以下的数列:
1 2 3 814 128 342 343 43 4249 654 687
第五步、根据百位数的数值,在走访数值(从前到后走访,反面步骤相同)时将它们分配至编号0到9的桶子中:
0 : 1 2 3 43
1 : 128
2 : 4249
3 : 342 343
4 :
5 :
6 : 654 687
7 :
8 : 814
9 :

第六步、接下来将这些桶子中的数值重新串接起来,成为以下的数列:
1 2 3 43 128 4249 342 343 654 687 814

。。。。。。反面的步骤各人应该都会走了吧。其实到了第六步的时候就剩 4249 没有排好序了。
从上面的步骤来看,很多的步骤都是相同的,因此肯定是个循环了,我们只需要控制个位、十位、百位、、、、就好了。
照旧看代码吧。
算法实现:
  1. //交换函数
  2. function swap(array &$arr,$a,$b){
  3.   $temp = $arr[$a];
  4.   $arr[$a] = $arr[$b];
  5.   $arr[$b] = $temp;
  6. }
  7. //获取数组中的最大数
  8. //就像上面的例子一样,我们最终是否停止算法不过就是看数组中的最大值:4249,它的位数就是循环的次数
  9. function getMax(array $arr){
  10.   $max = 0;
  11.   $length = count($arr);
  12.   for($i = 0;$i < $length;$i ++){
  13.     if($max < $arr[$i]){
  14.       $max = $arr[$i];
  15.     }
  16.   }
  17.   return $max;
  18. }
  19. //获取最大数的位数,最大值的位数就是我们分配桶的次数
  20. function getLoopTimes($maxNum){
  21.   $count = 1;
  22.   $temp = floor($maxNum / 10);
  23.   while($temp != 0){
  24.     $count ++;
  25.     $temp = floor($temp / 10);
  26.   }
  27.   return $count;
  28. }
  29. /**
  30. * @param array $arr 待排序数组
  31. * @param $loop 第几次循环标识
  32. * 该函数只是完成某一位(个位或十位)上的桶排序
  33. */
  34. function R_Sort(array &$arr,$loop){
  35.   //桶数组,在强类型语言中,这个数组应该声明为[10][count($arr)]
  36.   //第一维是 0-9 十个数
  37.   //第二维这样定义是因为有可能待排序的数组中的所有数的某一位上的只是一样的,这样就全挤在一个桶里面了
  38.   $tempArr = array();
  39.   $count = count($arr);
  40.   //初始化$tempArr数组
  41.   for($i = 0;$i < 10;$i ++){
  42.     $tempArr[$i] = array();
  43.   }
  44.   //求桶的index的除数
  45.   //如798个位桶index=(798/1)%10=8
  46.   //十位桶index=(798/10)%10=9
  47.   //百位桶index=(798/100)%10=7
  48.   //$tempNum为上式中的1、10、100
  49.   $tempNum = (int)pow(10, $loop - 1);
  50.   for($i = 0;$i < $count;$i ++){
  51.     //求出某位上的数字
  52.     $row_index = ($arr[$i] / $tempNum) % 10;
  53.     for($j = 0;$j < $count;$j ++){
  54.       if(@$tempArr[$row_index][$j] == NULL){
  55.         $tempArr[$row_index][$j] = $arr[$i];   //入桶
  56.         break;
  57.       }
  58.     }
  59.   }
  60.   //还原回原数组中
  61.   $k = 0;
  62.   for($i = 0;$i < 10;$i ++){
  63.     for($j = 0;$j < $count;$j ++){
  64.       if(@$tempArr[$i][$j] != NULL){
  65.         $arr[$k ++] = $tempArr[$i][$j];  //出桶
  66.         $tempArr[$i][$j] = NULL;  //避免下次循环的时候污染数据
  67.       }
  68.     }
  69.   }
  70. }
  71. //最终调用的主函数
  72. function RadixSort(array &$arr){
  73.   $max = getMax($arr);
  74.   $loop = getLoopTimes($max);
  75.   //对每一位进行桶分配(1 表示个位,$loop 表示最高位)
  76.   for($i = 1;$i <= $loop;$i ++){
  77.     R_Sort($arr,$i);
  78.   }
  79. }
复制代码
调用算法:
  1. $arr = array(2, 343, 342, 1, 128, 43, 4249, 814, 687, 654, 3);
  2. RadixSort($arr);
  3. var_dump($arr);
复制代码
运行效果:
  1. array(11) {
  2. [0]=>
  3. int(1)
  4. [1]=>
  5. int(2)
  6. [2]=>
  7. int(3)
  8. [3]=>
  9. int(43)
  10. [4]=>
  11. int(128)
  12. [5]=>
  13. int(342)
  14. [6]=>
  15. int(343)
  16. [7]=>
  17. int(654)
  18. [8]=>
  19. int(687)
  20. [9]=>
  21. int(814)
  22. [10]=>
  23. int(4249)
  24. }
复制代码
其实这些代码我是在挺早之前写的,今天在写博客的时候发现,其实桶就是一个队列,以是上面的
  1. R_Sort()
复制代码
函数复杂了,我们使用
  1. array_push()
复制代码
  1. array_shift()
复制代码
来重写该方法(当然,要模拟队列的话,用 SPL 提供的
  1. splqueue
复制代码
是最为得当的,在这里为了轻便我就不用了):
  1. function R_Sort(array &$arr,$loop){
  2.   $tempArr = array();
  3.   $count = count($arr);
  4.   for($i = 0;$i < 10;$i ++){
  5.     $tempArr[$i] = array();
  6.   }
  7.   //求桶的index的除数
  8.   //如798个位桶index=(798/1)%10=8
  9.   //十位桶index=(798/10)%10=9
  10.   //百位桶index=(798/100)%10=7
  11.   //$tempNum为上式中的1、10、100
  12.   $tempNum = (int)pow(10, $loop - 1);
  13.   for($i = 0;$i < $count;$i ++){
  14.     //求出某位上的数字
  15.     $row_index = ($arr[$i] / $tempNum) % 10;
  16.     //入桶
  17.     array_push($tempArr[$row_index],$arr[$i]);
  18.   }
  19.   //还原回原数组中
  20.   $k = 0;
  21.   for($i = 0;$i < 10;$i ++){
  22.     //出桶
  23.     while(count($tempArr[$i]) > 0){
  24.       $arr[$k ++] = array_shift($tempArr[$i]);
  25.     }
  26.   }
  27. }
复制代码
基数排序法是属于稳固性的排序,当时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数。
好了,到这里基数排序就已经给各人介绍完了。这个算法的总结重要是通过看网上的资料,以是就不再给出原作者了。
PS:这里再为各人推荐一款关于排序的演示工具供各人参考:
在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具:
http://tools.jb51.net/aideddesign/paixu_ys
更多关于PHP相关内容感兴趣的读者可查察本站专题:《php排序算法总结》、《PHP数据结构与算法教程》、《php程序设盘算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操纵本领大全》、《PHP常用遍历算法与本领总结》及《PHP数学运算本领总结》
希望本文所述对各人PHP程序设计有所帮助。

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作