思路

给定一个数组，内容都为数字
定义两个函数
1. 第一个函数负责分隔传入数组为两个子数组
  1. 如果传入数组只存在一个元素，则直接返回该元素
  2. 否则分隔传入数组为两个数组，为左、右
  3. 执行第二个函数，参数①为第一个函数带参数左，参数②为第一个函数带参数右(也就是说自上而下的直到只剩1个元素在两个数组，自下而上来看就是不停对两个有序数组进行合并并且这时第二个函数返回的合并两个有序数组的数组将是绝对有序的)
  4. 并获取返回值
2. 第二个函数负责对传入的两个数组一一比较大小，返回一个拼接在一起的相对有序的数组
  1. 循环判断传入的两个数组是否为空
    1. 若左数组第一个元素小于右数组第一个元素
      1. 将左数组第一个元素加入结果集
      2. 删除左数组第一个元素(shift)
    2. 否则
      1. 将右数组第一个元素加入结果集
      2. 删除右数组第一个元素(shift)
  2. 循环判断左右数组是否存在值
    1. 将值直接加入结果集(无需担心顺序，两个有序数组合并时不会存在在左右数组有剩余)
执行第一个函数，获取返回值
得到一个升序数组

代码

<?php

$array = array(2,4,1,7,714,492);

function mergesort($array){
    $count = count($array);
    $mid = floor($count / 2);
    if($count < 2): //递归mergesort直到数组中只有1个元素，交给merge比较大小存入结果集
        return $array;
    endif;
    $right = array_slice($array,0,$mid); //从0开始往后截取$mid个数值(不包含本身)，返回剩余数组内容
    $left = array_slice($array,$mid);
    return merge(mergesort($left),mergesort($right));
    /*
        return merge(return merge(...),return merge(...))
        1,2,3,4
        1,2 | 3,4
        1 | 2  |  3 | 4
    */
}

function merge($left,$right){
    $result = array();
    while(count($left) > 0 && count($right) >0){ //count函数动态判断数组长度
        if($left[0] <= $right[0]){
            $result[] = array_shift($left); //左边小于右边，将左边存入结果集，在左边数组删除当前元素
        }else{
            $result[] = array_shift($right);
        }
    }
    while(count($left) > 0){
        $result[] = array_shift($left);
    }
    while(count($right) > 0){
        $result[] = array_shift($right);
    }
    return $result; //返回本轮结果集
}


$array = mergesort($array);
var_dump($array);

?>

PHP函数

array_shift(array) 函数

删除数组中的第一个元素，并返回被删除元素的值

array_slice(array,start,end) 函数

从数组的第start个元素开始取出，并返回数组中的其余元素

end 默认为数组长度(也就是说此函数取出不包含下标为end的元素)

算法学习之路 | 归并排序[Php]

Subscribe

Comments