[PHP]算法-归并排序的PHP落成

 

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代码完成

<?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);
}

以上就是本文的全体内容,希望对我们的就学抱有支持,也期望我们多多接济帮客之家。

http://www.bkjia.com/PHPjc/1266783.htmlwww.bkjia.comtruehttp://www.bkjia.com/PHPjc/1266783.htmlTechArticlePHP排序算法系列之归并排序详解,排序算法归并详解
归并排序
归并排序(MERGE-SORT)是建立在统一操作上的一种有效的排序算法,该算法是采…

 

<?php
//归并排序

function merge(&$A,$left,$mid,$right,$temp){
        //7.左堆起始
        $i=$left;
        //8.右堆起始
        $j=$mid+1;
        //9.临时数组起始
        $t=0;
        //10.左右堆数组都没到末尾
        while($i<=$mid && $j<=$right){
                //11.左堆小于等于右堆时
                if($A[$i]<=$A[$j]){
                        //12.左堆赋给临时数组,索引加1
                        $temp[$t++]=$A[$i++];
                }else{
                        //13.右堆赋给临时数组,索引加1
                        $temp[$t++]=$A[$j++];
                }   
        }   
        //14.左堆剩余的全部加进临时数组
        while($i<=$mid){
                $temp[$t++]=$A[$i++];
        }   
        //15.右堆剩余全部加进临时数组
        while($j<=$right){
                $temp[$t++]=$A[$j++];
        }   
        //16.临时数组的元素重新赋回原数组
        for($i=0;$i<$t;$i++){
                $A[$left+$i]=$temp[$i];
        }   
}

//1.利用分治法思想,递归的切分排序元素
function mergeSort(&$A,$left,$right,$temp){
        //2.最左只能小于最右,等于的时候就一个元素,大于是不可能的
        if($left<$right){
                //3.获取中间的元素
                $mid=intval(($left+$right)/2);
                //4.递归左半区
                mergeSort($A,$left,$mid,$temp);
                //5.递归右半区
                mergeSort($A,$mid+1,$right,$temp);
                //6.合并两个有序数组为一个有序数组
                merge($A,$left,$mid,$right,$temp);
        }    
}

$A=array(2,4,6,1,5,7,3,8,9);
$temp=array();
mergeSort($A,0,count($A)-1,$temp);
var_dump($A);

  

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图