php实现归并排序算法

理解

归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。
如　设有数列{6，202，100，301，38，8，1}
初始状态：6,202,100,301,38,8,1
第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；
第三次归并后：{1,6,8,38,100,202,301},比较次数：4；
总的比较次数为：3+4+4=11；
逆序数为14；
归并排序是稳定的排序，速度仅次于快速排序

代码实现

<?php
/**
 * Created by PhpStorm.
 * User: benny
 * Date: 18-12-2
 * Time: 上午9:42
 */
/**
 * 归并排序
 * @param array $array
 * @return array
 *
 */
function all_merge_sort($array=[]){
    $count = count($array);
    //递归结束条件,到达这步的时候,数组就只剩下一个元素了,也就是分离了数组
    if ($count<=1){
        return $array;
    }
    $mid = intval($count/2);

    //拆分数组0-mid这部分给左边left_array
    $left_array = array_slice($array,0,$mid);

    //拆分数组mid-末尾这部分给右边right_array
    $right_array = array_slice($array,$mid);

    //左边拆分完后开始递归合并往上走
    $left_array = all_merge_sort($left_array);

    //右边拆分完毕开始递归往上走
    $right_array = all_merge_sort($right_array);

    //合并两个数组,继续递归
    $return_array = merge_sort($left_array,$right_array);
    return $return_array;
}

/**
 * @param $left_array
 * @param $right_array
 * @return array
 *
 * merge函数将指定的两个有序数组(arr1,arr2)合并并且排序
我们可以找到第三个数组,然后依次从两个数组的开始取数据哪个数据小就先取哪个的,然后删除掉刚刚取过///的数据
 */
function merge_sort($left_array,$right_array){
    $return_array = [];
    while (count($left_array) && count($right_array)){
        //这里不断的判断哪个值小,就将小的值给到arrC,但是到最后肯定要剩下几个值,
        //不是剩下arrA里面的就是剩下arrB里面的而且这几个有序的值,肯定比arrC里面所有的值都大所以使用
        $return_array[] = $left_array[0] < $right_array[0] ? array_shift($left_array): array_shift($right_array);
    }
    return array_merge($return_array,$left_array,$right_array);
}

$array=[12,5,4,32,56,87,4,11,2,0];
print_r(json_encode(all_merge_sort($array)));