我們先看歸并排序的定義
歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用斗忌。將已有序的子序列合并，得到完全有序的序列旺聚；即先使每個(gè)子序列有序织阳，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表砰粹，稱為二路歸并唧躲。
簡(jiǎn)單來說就是將兩個(gè)有序表合并成一個(gè)有序表。
我們先通過下圖來了解一下歸并排序的流程碱璃。
歸并排序流程
下面我們來看如何分解然后再合并的步驟
- 申請(qǐng)空間弄痹，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列
- 設(shè)定兩個(gè)指針嵌器，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
- 比較兩個(gè)指針?biāo)赶虻脑馗卣妫x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置
- 重復(fù)步驟3直到某一指針達(dá)到序列尾
- 將另一序列剩下的所有元素直接復(fù)制到合并序列尾
最后我們用PHP實(shí)現(xiàn)了歸并排序的算法
function Merge($arr,$l,$m,$r){
$t = $arr;
$start = $l;
$end = $m+1;
while($l<=$r){
if($l>$m||$end>$r) break;
if($arr[$l]<$arr[$end]){
$t[$start++] = $arr[$l++];
}else{
$t[$start++] = $arr[$end++];
}
}
if($l<=$m){
$s = $l;
$e = $m;
}elseif($r>=$end){
$s = $end;
$e = $r;
}
while($s<=$e){
$t[$start++] = $arr[$s++];
}
$arr = $t;
return $arr;
}
function MergeSort(&$arr,$l,$r){
if($r <= $l) return ;
$m = floor(($l+$r)/2);
MergeSort($arr,$l,$m);
MergeSort($arr,$m+1,$r);
$arr = Merge($arr,$l,$m,$r);
}
$arr = array(10,6,8,23,4,1,17,56,32,50,11,9);
MergeSort($arr,0,count($arr)-1);
print_r($arr);
上面代碼是使用遞歸的機(jī)制實(shí)現(xiàn)的爽航，當(dāng)然也可以使用非遞歸的形式來實(shí)現(xiàn)蚓让，大家可以參考《歸并排序（非遞歸實(shí)現(xiàn)）》這篇文章。
用PHP實(shí)現(xiàn)歸并排序岳掐，按照上面的代碼來說凭疮，其代碼比較繁瑣。PHP有其自己的特色串述，可以用更少的代碼來實(shí)現(xiàn)歸并排序执解。但是上述代碼更能體現(xiàn)整個(gè)分解和合并的過程。所以如果是學(xué)習(xí)歸并排序算法的話，建議使用上述代碼衰腌，雖說代碼繁瑣新蟆，但是對(duì)于理解歸并排序的過程有很大的幫助。
更詳細(xì)的歸并排序的算法我新寫了一篇文章全面了解歸并排序算法右蕊，大家可以參考琼稻。
