欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-05-04 14:08:46

 

 

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