[PHP]算法-归并排序的PHP实现

2018-09-01 05:53:16来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

 

 

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

  

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:PHP导出数据到表格的实例

下一篇:面向对象程序的设计模式-单例模式