算法原理

下列動(dòng)圖來(lái)自@五分鐘學(xué)算法，演示了歸并算法的原理和步驟。

原理:

利用遞歸，先拆分、后合并、再排序。

步驟:

• 均分?jǐn)?shù)列為兩個(gè)子數(shù)列
• 遞歸重復(fù)上一步驟，直到子數(shù)列只有一個(gè)元素
• 父數(shù)列合并兩個(gè)子數(shù)列并排序，遞歸返回?cái)?shù)列

代碼實(shí)現(xiàn)

// 歸并排序主程序 function mergeSort($arr) {$len = count($arr);if ($len <= 1) {return $arr;} // 遞歸結(jié)束條件, 到達(dá)這步的時(shí)候, 數(shù)組就只剩下一個(gè)元素了, 也就是分離了數(shù)組$mid = intval($len / 2); // 取數(shù)組中間$left = array_slice($arr, 0, $mid); // 拆分?jǐn)?shù)組0-mid這部分給左邊left$right = array_slice($arr, $mid); // 拆分?jǐn)?shù)組mid-末尾這部分給右邊right$left = mergeSort($left); // 左邊拆分完后開(kāi)始遞歸合并往上走$right = mergeSort($right); // 右邊拆分完畢開(kāi)始遞歸往上走$arr = merge($left, $right); // 合并兩個(gè)數(shù)組,繼續(xù)遞歸return $arr; }// merge函數(shù)將指定的兩個(gè)有序數(shù)組(arrA, arr)合并并且排序 function merge($arrA, $arrB) {$arrC = array();while (count($arrA) && count($arrB)) {// 這里不斷的判斷哪個(gè)值小, 就將小的值給到arrC, 但是到最后肯定要剩下幾個(gè)值,// 不是剩下arrA里面的就是剩下arrB里面的而且這幾個(gè)有序的值, 肯定比arrC里面所有的值都大所以使用$arrC[] = $arrA[0] < $arrB[0] ? array_shift($arrA) : array_shift($arrB);}return array_merge($arrC, $arrA, $arrB); }

測(cè)試:

$startTime = microtime(1);$arr = range(1, 10); shuffle($arr);echo "before sort: ", implode(', ', $arr), "\n"; $sortArr = mergeSort($arr); echo "after sort: ", implode(', ', $sortArr), "\n";echo "use time: ", microtime(1) - $startTime, "s\n";

時(shí)間復(fù)雜度

歸并排序的時(shí)間復(fù)雜度是 O(N*lgN)。

假設(shè)被排序的數(shù)列中有 N 個(gè)數(shù)。遍歷一趟的時(shí)間復(fù)雜度是 O(N)，需要遍歷多少次呢？

歸并排序的形式就是一棵二叉樹(shù)，它需要遍歷的次數(shù)就是二叉樹(shù)的深度，而根據(jù)完全二叉樹(shù)的可以得出它的時(shí)間復(fù)雜度是 O(N*lgN)。

參考資料

• 歸并排序
• 十大經(jīng)典排序算法動(dòng)畫與解析

---

感謝您的閱讀，覺(jué)得內(nèi)容不錯(cuò)，點(diǎn)個(gè)贊吧 ?

原文地址: https://shockerli.net/post/me...

總結(jié)

以上是生活随笔為你收集整理的PHP 实现归并排序算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。