当前位置:Gxlcms > PHP教程 > PHP排序算法系列之归并排序详解

PHP排序算法系列之归并排序详解

时间:2021-07-01 10:21:17 帮助过:42人阅读

本篇讲解PHP排序算法系列之归并排序详解。

归并排序

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

归并过程

归并排序的核心就是如何将两个有序序列进行合并,假定有两个有序数组,比较两个有序数组的首个元素,谁小就取谁,并将该元素放入第三个数组中,取了之后在相应的数组中将删除此元素,依次类推,当取到一个数组已经没有元素时,就可将另一数组的剩余元素直接添加到第三个数组中。

原理

1、将序列每相邻两个数字进行归并操作,形成ceil(n/2)个序列,排序后每个序列包含两个元素,最后一个序列可能只有一个元素。

2、将上述序列再次归并,形成ceil(n/4)个序列,每个序列包含四个元素,最后一个序列可能只有三个及以下元素。

3、重复步骤2,直到所有元素排序完毕。

举例

对数组[53,89,12,6,98,25,37,92,5]进行排序

第一次归并后

(53,89),12,(6,98),(25,37),(5,92)

第二次归并后

(12,53,89),(6,25,37,98),(5,92)

第三次归并后

(6,12,25,37,53,89,98),(5,92)

第四次归并后

5,6,12,25,37,53,89,92,98

PHP代码实现

function merge_sort($arr){
 
$length=count($arr);
 
if($length<=1){
 
return $arr;
 
}
 
//分解数组,递归排序
 
$half=ceil($length/2);
 
$arr2=array_chunk($arr,$half);
 
$left=merge_sort($arr2[0]);
 
$right=merge_sort($arr2[1]);
 
while(count($left)&&count($right)){
 
if($left[0]<$right[0]){
 
$reg[]=array_shift($left);
 
}else{
 
$reg[]=array_shift($right);
 
}
 
}
 
return array_merge($reg,$left,$right);
 
}

本篇讲解PHP排序算法系列之归并排序详解,耕读相关内容请关注Gxl网。

相关推荐:

thinkPHP5框架数据库连贯操作:cache()用法详情

PHP接口多继承和tarits实现多继承效果的方法教程详情

PHP 如何获取某年第几周的开始日期和结束日期教程

以上就是PHP排序算法系列之归并排序详解的详细内容,更多请关注Gxl网其它相关文章!

人气教程排行