[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地图