php实现归并排序（Merge Sort）

归并排序

        基本思想: 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

算法描述

把长度为n的输入序列分成两个长度为n/2的子序列；

对这两个子序列分别采用归并排序；

将两个排序好的子序列合并成一个最终的排序序列。

图片描述

代码实现(php）

<?php
$arr=array(1,2,3,5,2,3,9,8,3,2,7,4,9,);
function merge_sort(&$arr){
    $len=count($arr);
    if($len==1)
        return $arr;
    $middle=intval($len/2);
    $left=array_slice($arr,0,$middle);
    $right=array_slice($arr,$middle);
    merge_sort($left);
    merge_sort($right);
    $arr=merge($left,$right);
}
function merge($leftarr,$rightarr){
    $arrmerge=array();
    while(count($leftarr) && count($rightarr))
        $arrmerge[]=$leftarr[0]<$rightarr[0]?array_shift($leftarr):array_shift($rightarr);
    return array_merge($arrmerge,$leftarr,$rightarr);
}
merge_sort($arr);
var_dump($arr);
function printArr($arr){
    for($i=0;$i<count($arr);$i++)
        echo ' '.$arr[$i];
}