理解
归并操作(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)));
