PHP排序演算法系列之歸併排序詳解

本篇講解PHP排序演算法系列之歸併排序詳解。

歸併排序

歸併排序(MERGE-SORT)是建立在歸併操作上的一種有效的排序演算法,該演算法是採用分治法(Divide and Conquer)的一個非常典型的應用。將已有序的子序列合併，得到完全有序的序列;即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合併成一個有序表，稱為二路歸併。

歸併過程

歸併排序的核心就是如何將兩個有序序列進行合併，假定有兩個有序數組，比較兩個有序數組的首個元素，誰小就取誰，並將該元素放入第三個數組中，取了之後在對應的數組中將刪除此元素，依次類推，當取到一個數組已經沒有元素時，就可將另一數組的剩餘元素直接加到第三個陣列中。

原理

1、將序列每相鄰兩個數字進行歸併操作，形成ceil(n/2)個序列，排序後每個序列包含兩個元素,最後一個序列可能只有一個元素。

2、將上述序列再次歸併，形成ceil(n/4)個序列，每個序列包含四個元素，最後一個序列可能只有三個及以下元素。

3、重複步驟2，直到所有元素都排序完畢。

舉例

對陣列[53,89,12,6,98,25,37,92,5]排序

第一次歸併後

(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程式碼實作

function merge_sort($arr){
 
$length=count($arr);
 
if($length<=1){
 
return $arr;
 
}
 
//分解数组，递归排序
 
$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);
 
}

   本篇講解PHP排序演算法系列之歸併排序詳解，耕讀相關內容請關注php中文網。

相關推薦：

thinkPHP5框架資料庫連貫操作：cache()用法詳情

PHP介面多重繼承和tarits實現多重繼承效果的方法教學詳情

PHP 如何取得某年第幾週的開始日期和結束日期教學

#######

以上是PHP排序演算法系列之歸併排序詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！