理解
歸并操作(merge)兰绣，也叫歸并算法世分，指的是將兩個(gè)順序序列合并成一個(gè)順序序列的方法。
如 設(shè)有數(shù)列{6缀辩，202臭埋，100踪央，301，38瓢阴，8畅蹂，1}
初始狀態(tài)：6,202,100,301,38,8,1
第一次歸并后：{6,202},{100,301},{8,38},{1}，比較次數(shù)：3荣恐；
第二次歸并后：{6,100,202,301}液斜，{1,8,38}，比較次數(shù)：4叠穆；
第三次歸并后：{1,6,8,38,100,202,301},比較次數(shù)：4少漆；
總的比較次數(shù)為：3+4+4=11；
逆序數(shù)為14硼被；
歸并排序是穩(wěn)定的排序示损，速度僅次于快速排序
代碼實(shí)現(xiàn)
<?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);
//遞歸結(jié)束條件,到達(dá)這步的時(shí)候,數(shù)組就只剩下一個(gè)元素了,也就是分離了數(shù)組
if ($count<=1){
return $array;
}
$mid = intval($count/2);
//拆分?jǐn)?shù)組0-mid這部分給左邊left_array
$left_array = array_slice($array,0,$mid);
//拆分?jǐn)?shù)組mid-末尾這部分給右邊right_array
$right_array = array_slice($array,$mid);
//左邊拆分完后開始遞歸合并往上走
$left_array = all_merge_sort($left_array);
//右邊拆分完畢開始遞歸往上走
$right_array = all_merge_sort($right_array);
//合并兩個(gè)數(shù)組,繼續(xù)遞歸
$return_array = merge_sort($left_array,$right_array);
return $return_array;
}
/**
* @param $left_array
* @param $right_array
* @return array
*
* merge函數(shù)將指定的兩個(gè)有序數(shù)組(arr1,arr2)合并并且排序
我們可以找到第三個(gè)數(shù)組,然后依次從兩個(gè)數(shù)組的開始取數(shù)據(jù)哪個(gè)數(shù)據(jù)小就先取哪個(gè)的,然后刪除掉剛剛?cè)∵^///的數(shù)據(jù)
*/
function merge_sort($left_array,$right_array){
$return_array = [];
while (count($left_array) && count($right_array)){
//這里不斷的判斷哪個(gè)值小,就將小的值給到arrC,但是到最后肯定要剩下幾個(gè)值,
//不是剩下arrA里面的就是剩下arrB里面的而且這幾個(gè)有序的值,肯定比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)));
