菜单

PHP排序算法种类之归并排序详解,排序算法归并详解

2019年1月30日 - Php

 

PHP排序算法体系之归并排序详解,排序算法归并详解

归并排序

归并排序(MERGE-SORT)是起家在联合操作上的一种有效的排序算法,该算法是采纳分治法(Divide
and
Conquer)的一个要命出众的运用。将已有序的子系列合并,得到完全有序的种类;即先使每个子体系有序,再使子系列段间有序。若将八个不变表合并成一个平稳表,称为二路归并。

归并经过

归并排序的中坚就是何许将多少个静止种类进行联合,假定有三个有序数组,比较四个有序数组的第四个因素,何人小就取什么人,并将该因素放入第多个数组中,取了之后在对应的数组中将删除此元素,依次类推,当取到一个数组已经没有元素时,就可将另一数组的剩余元素直接抬高到第两个数组中。

manbetx网页手机登录版,原理

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