PHP排序算法系列之歸并排序詳解
歸并排序
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
歸并過程
歸并排序的核心就是如何將兩個有序序列進行合并，假定有兩個有序數(shù)組，比較兩個有序數(shù)組的首個元素，誰小就取誰，并將該元素放入第三個數(shù)組中，取了之后在相應的數(shù)組中將刪除此元素，依次類推，當取到一個數(shù)組已經(jīng)沒有元素時，就可將另一數(shù)組的剩余元素直接添加到第三個數(shù)組中。
原理
1、將序列每相鄰兩個數(shù)字進行歸并操作，形成ceil(n/2)個序列，排序后每個序列包含兩個元素,最后一個序列可能只有一個元素。
2、將上述序列再次歸并，形成ceil(n/4)個序列，每個序列包含四個元素，最后一個序列可能只有三個及以下元素。
3、重復步驟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);
}
以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
優(yōu)化PHP代碼的50條建議，學習php的朋友可以看下，有助于提高php效率2008-03-03
這篇文章主要介紹了php實現(xiàn)mysql備份恢復分卷處理的方法,包括完整的MySQL備份恢復類文件及用法實例,注釋包含了詳盡的用法說明,是非常實用的技巧,需要的朋友可以參考下2014-12-12
PHP常用排序算法實例小結(jié)【基本排序，冒泡排序，快速排序，插入排序】
這篇文章主要介紹了PHP常用排序算法,結(jié)合實例形式總結(jié)分析了php常見的排序算法,包括基本排序、冒泡排序、快速排序、插入排序等,需要的朋友可以參考下2017-02-02
在本篇文章里小編給大家分享了關于php中訪問修飾符的知識點總結(jié)，興趣的朋友們可以學習參考下。2019-01-01
php set_time_limit(0) 設置程序執(zhí)行時間的函數(shù)
一個簡單的例子，在網(wǎng)頁里顯示1500條語句，如果未設置失效時間，則程序執(zhí)行到791時結(jié)束了，如果把 set_time_limit(0); 前的注釋符//去除，則程序直到1才結(jié)束。2010-05-05
PHP用戶管理中常用接口調(diào)用實例及解析（含源碼）
本文主要介紹了PHP用戶管理中常用接口調(diào)用實例及解析（含源碼），具有很好的參考價值。下面跟著小編一起來看下吧2017-03-03
php實現(xiàn)網(wǎng)站頂踩功能的完整前端代碼
這篇文章主要介紹了php實現(xiàn)網(wǎng)站頂踩功能的完整前端代碼的相關資料,需要的朋友可以參考下2015-07-07
PHP中通過HTTP_USER_AGENT判斷是否為手機移動終端的函數(shù)代碼
經(jīng)常我們需要做一些判斷是否是手機訪問的時候，然后進行自動跳轉(zhuǎn)操作，這是從一個PHP框架分離出來的一段判斷是否為手機移動終端的函數(shù)，分享下2013-02-02
利用瀏覽器的Javascript控制臺調(diào)試PHP程序
現(xiàn)在，越來越多的瀏覽器都有了開發(fā)這工具或者Javascript控制臺，通過這些工具，我們可以很方便的顯示PHP代碼中的變量或數(shù)組值2014-01-01
本文主要介紹了解決PHP編輯器PhpStrom運行緩慢問題的方法，具有很好的參考價值，下面跟著小編一起來看下吧2017-02-02