归并排序

定义 : 是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

示例代码 :

<?php
// 主程序
function merge_sort($arr){
    $len=count($arr);
    if($len<=1){
        return $arr;
    }
    $mid=intval($len/2); // 中间索引 按照中间索引 将数组半劈
    $left=array_slice($arr,0,$mid); // 前半段
    $right=array_slice($arr,$mid); // 后半段,第三个参数不写,代表取到结尾
    $left=merge_sort($left); // 递归拆左
    $right=merge_sort($right); // 递归拆右
    // 合并并排序
    return merge($left,$right);
}
// 合并排序辅助函数
function merge($arr1,$arr2){
    $arr3=[];
    while (count($arr1) and count($arr2)){
        // array_shift删除数组的第一个元素 并将其返回
        $arr3[]=$arr1[0]<$arr2[0]?array_shift($arr1):array_shift($arr2);
    }
    return array_merge($arr3,$arr1,$arr2);// $arr1或者$arr2可能会剩下一个最大值 将其放至末尾
}
$arr=[4,1,6,5,7,9,3,2];
echo "<pre>";
print_r(merge_sort($arr));
echo "</pre>";