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