您好,登錄后才能下訂單哦!
小編給大家分享一下PHP排序算法系列之歸并排序的示例分析,希望大家閱讀完這篇文章之后都有所收獲,下面讓我們一起去探討吧!
歸并排序
歸并排序(MERGE-SORT)是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法(Divide and Conquer)的一個非常典型的應(yīng)用。將已有序的子序列合并,得到完全有序的序列;即先使每個子序列有序,再使子序列段間有序。若將兩個有序表合并成一個有序表,稱為二路歸并。
歸并過程
歸并排序的核心就是如何將兩個有序序列進行合并,假定有兩個有序數(shù)組,比較兩個有序數(shù)組的首個元素,誰小就取誰,并將該元素放入第三個數(shù)組中,取了之后在相應(yīng)的數(shù)組中將刪除此元素,依次類推,當(dāng)取到一個數(shù)組已經(jīng)沒有元素時,就可將另一數(shù)組的剩余元素直接添加到第三個數(shù)組中。
原理
1、將序列每相鄰兩個數(shù)字進行歸并操作,形成ceil(n/2)個序列,排序后每個序列包含兩個元素,最后一個序列可能只有一個元素。
2、將上述序列再次歸并,形成ceil(n/4)個序列,每個序列包含四個元素,最后一個序列可能只有三個及以下元素。
3、重復(fù)步驟2,直到所有元素排序完畢。
舉例
對數(shù)組[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代碼實現(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); }
看完了這篇文章,相信你對“PHP排序算法系列之歸并排序的示例分析”有了一定的了解,如果想了解更多相關(guān)知識,歡迎關(guān)注億速云行業(yè)資訊頻道,感謝各位的閱讀!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。