歸并排序

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（pide 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代碼實現

 ?phpfunction 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排序算法系列之直接選擇排序的詳解

PHP排序算法系列之插入排序的詳解

PHP實現桶排序算法的講解

以上就是PHP排序算法系列之歸并排序詳解_php技巧的詳細內容，PHP教程

鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯系我們修改或刪除，多謝。