歸并排序
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。
歸并過程
歸并排序的核心就是如何將兩個(gè)有序序列進(jìn)行合并，假定有兩個(gè)有序數(shù)組，比較兩個(gè)有序數(shù)組的首個(gè)元素，誰(shuí)小就取誰(shuí)，并將該元素放入第三個(gè)數(shù)組中，取了之后在相應(yīng)的數(shù)組中將刪除此元素，依次類推，當(dāng)取到一個(gè)數(shù)組已經(jīng)沒有元素時(shí)，就可將另一數(shù)組的剩余元素直接添加到第三個(gè)數(shù)組中。
原理
1、將序列每相鄰兩個(gè)數(shù)字進(jìn)行歸并操作，形成ceil(n/2)個(gè)序列，排序后每個(gè)序列包含兩個(gè)元素,最后一個(gè)序列可能只有一個(gè)元素。
2、將上述序列再次歸并，形成ceil(n/4)個(gè)序列，每個(gè)序列包含四個(gè)元素，最后一個(gè)序列可能只有三個(gè)及以下元素。
3、重復(fù)步驟2，直到所有元素排序完畢。
舉例
對(duì)數(shù)組[53,89,12,6,98,25,37,92,5]進(jìn)行排序
第一次歸并后
(53,89),12，(6,98),(25,37),(5,92)
第二次歸并后
(12,53,89),(6,25,37,98),(5,92)
第三次歸并后
(6,12,25,37,53,89,98),(5,92)
第四次歸并后
5,6,12,25,37,53,89,92,98
PHP代碼實(shí)現(xiàn)
<?php
function merge_sort($arr){
$length=count($arr);
if($length<=1){
return $arr;
}
//分解數(shù)組，遞歸排序
$half=ceil($length/2);
$arr2=array_chunk($arr,$half);
$left=merge_sort($arr2[0]);
$right=merge_sort($arr2[1]);
while(count($left)&&count($right)){
if($left[0]<$right[0]){
$reg[]=array_shift($left);
}else{
$reg[]=array_shift($right);
}
}
return array_merge($reg,$left,$right);
}
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持。