• 售前

  • 售后

热门帖子
入门百科

PHP排序算法之归并排序(Merging Sort)实例详解

[复制链接]
迟到399 显示全部楼层 发表于 2021-10-25 20:32:03 |阅读模式 打印 上一主题 下一主题
本文实例报告了PHP排序算法之归并排序(Merging Sort)。分享给大家供大家参考,具体如下:
根本头脑:
归并排序:就是利用归并(归并)的头脑实现的排序方法。它的原理是假设初始序列含有 n 个元素,则可以看成是 n 个有序的子序列,每个子序列的长度为 1,然后两两归并,得到 ⌈ n / 2⌉ (⌈ x ⌉ 表现不小于 x 的最小整数)个长度为 2 或 1 的有序序列;再两两归并,······,如此重复,直至得到一个长度为 n 的有序序列为止,这种排序方法就成为 2 路归并排序。
一、归并的过程:
a 取 a 数组的前部门(已经排好序),a[j] 取 a 数组的后部门(已经排好序)
r 数组存储排好序的 a 数组
比力 a和 a[j] 的大小,若 a ≤ a[j],则将第一个有序表中的元素 a 复制到 r[k] 中,并令 i 和 k 分别加上 1;否则将第二个有序表中的元素 a[j] 复制到 r[k] 中,并令 j 和 k 分别加上 1,如此循环下去,直到此中一个有序表取完,然后再将另一个有序表中剩余的元素复制到 r 中从下标 k 到下标 t 的单元。归并排序的算法我们通常用递归实现,先把待排序区间 [s,t] 以中点二分,接着把左边子区间排序,再把右边子区间排序,末了把左区间和右区间用一次归并操作归并成有序的区间 [s,t]。
二、归并操作:
归并操作(merge),也叫归并算法,指的是将两个次序序列归并成一个次序序列的方法。
如 设有数列{6,202,100,301,38,8,1}
初始状态:6 , 202 , 100 , 301 , 38 , 8,1
第一次归并后:{6,202},{100,301},{8,38},{1},比力次数:3;
第二次归并后:{6,100,202,301},{1,8,38},比力次数:4;
第三次归并后:{1,6,8,38,100,202,301},比力次数:4;
总的比力次数为:3+4+4=11,;
逆序数为14;
三、算法形貌:
归并操作的工作原理如下:
第一步:申请空间,使其大小为两个已经排序序列之和,该空间用来存放归并后的序列
第二步:设定两个指针,最初位置分别为两个已经排序序列的起始位置
第三步:比力两个指针所指向的元素,选择相对小的元素放入到归并空间,并移动指针到下一位置
重复步调3直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到归并序列尾

算法实现:
我们先来看看主函数部门:
  1. //交换函数
  2. function swap(array &$arr,$a,$b){
  3.   $temp = $arr[$a];
  4.   $arr[$a] = $arr[$b];
  5.   $arr[$b] = $temp;
  6. }
  7. //归并算法总函数
  8. function MergeSort(array &$arr){
  9.   $start = 0;
  10.   $end = count($arr) - 1;
  11.   MSort($arr,$start,$end);
  12. }
复制代码
在总函数中,我们只调用了一个 MSort() 函数,由于我们要利用递归调用,以是将 MSort() 封装起来。
下面我们来看看
  1. MSort()
复制代码
函数:
  1. function MSort(array &$arr,$start,$end){
  2.   //当子序列长度为1时,$start == $end,不用再分组
  3.   if($start < $end){
  4.     $mid = floor(($start + $end) / 2); //将 $arr 平分为 $arr[$start - $mid] 和 $arr[$mid+1 - $end]
  5.     MSort($arr,$start,$mid);  //将 $arr[$start - $mid] 归并为有序的$arr[$start - $mid]
  6.     MSort($arr,$mid + 1,$end);  //将 $arr[$mid+1 - $end] 归并为有序的 $arr[$mid+1 - $end]
  7.     Merge($arr,$start,$mid,$end);    //将$arr[$start - $mid]部分和$arr[$mid+1 - $end]部分合并起来成为有序的$arr[$start - $end]
  8.   }
  9. }
复制代码
上面的
  1. MSort()
复制代码
函数实现将数组分半再分半(直到子序列长度为1),然后将子序列归并起来。
如今是我们的归并操作函数
  1. Merge()
复制代码
:
  1. //归并操作
  2. function Merge(array &$arr,$start,$mid,$end){
  3.   $i = $start;
  4.   $j=$mid + 1;
  5.   $k = $start;
  6.   $temparr = array();
  7.   while($i!=$mid+1 && $j!=$end+1)
  8.   {
  9.     if($arr[$i] >= $arr[$j]){
  10.       $temparr[$k++] = $arr[$j++];
  11.     }
  12.     else{
  13.       $temparr[$k++] = $arr[$i++];
  14.     }
  15.   }
  16.   //将第一个子序列的剩余部分添加到已经排好序的 $temparr 数组中
  17.   while($i != $mid+1){
  18.     $temparr[$k++] = $arr[$i++];
  19.   }
  20.   //将第二个子序列的剩余部分添加到已经排好序的 $temparr 数组中
  21.   while($j != $end+1){
  22.     $temparr[$k++] = $arr[$j++];
  23.   }
  24.   for($i=$start; $i<=$end; $i++){
  25.     $arr[$i] = $temparr[$i];
  26.   }
  27. }
复制代码
到了这里,我们的归并算法就完了。我们调用试试:
  1. $arr = array(9,1,5,8,3,7,4,6,2);
  2. MergeSort($arr);
  3. var_dump($arr);
复制代码
运行结果:
  1. array(9) {
  2. [0]=>
  3. int(1)
  4. [1]=>
  5. int(2)
  6. [2]=>
  7. int(3)
  8. [3]=>
  9. int(4)
  10. [4]=>
  11. int(5)
  12. [5]=>
  13. int(6)
  14. [6]=>
  15. int(7)
  16. [7]=>
  17. int(8)
  18. [8]=>
  19. int(9)
  20. }
复制代码
复杂度分析:
由于归并算法无论原来的序列是否有序都会举行分组和比力,因此它的最好、最坏、平均的时间复杂度都是 O(nlogn)
归并算法是一种稳固的排序算法。
本文参考自《大话数据布局》,在此仅作纪录,方便以后查阅,大神勿喷!
PS:这里再为大家保举一款关于排序的演示工具供大家参考:
在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具:
http://tools.jb51.net/aideddesign/paixu_ys
更多关于PHP相关内容感爱好的读者可查看本站专题:《php排序算法总结》、《PHP数据布局与算法教程》、《php步伐计划算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作本领大全》、《PHP常用遍历算法与本领总结》及《PHP数学运算本领总结》
盼望本文所述对大家PHP步伐计划有所帮助。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

帖子地址: 

回复

使用道具 举报

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

本版积分规则

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

  • 微信公众号

  • 商务合作