資訊專欄INFORMATION COLUMN
摘要：算法原理下列動圖來自五分鐘學算法，演示了歸并算法的原理和步驟。原理利用遞歸，先拆分后合并再排序。假設被排序的數列中有個數。參考資料歸并排序十大經典排序算法動畫與解析感謝您的閱讀，覺得內容不錯，點個贊吧
算法原理
下列動圖來自@五分鐘學算法，演示了歸并算法的原理和步驟。
原理:
利用遞歸，先拆分、后合并、再排序。
步驟:
均分數列為兩個子數列
遞歸重復上一步驟，直到子數列只有一個元素
父數列合并兩個子數列并排序，遞歸返回數列
代碼實現// 歸并排序主程序
function mergeSort($arr) {
$len = count($arr);
if ($len <= 1) {
return $arr;
} // 遞歸結束條件, 到達這步的時候, 數組就只剩下一個元素了, 也就是分離了數組
$mid = intval($len / 2); // 取數組中間
$left = array_slice($arr, 0, $mid); // 拆分數組0-mid這部分給左邊left
$right = array_slice($arr, $mid); // 拆分數組mid-末尾這部分給右邊right
$left = mergeSort($left); // 左邊拆分完后開始遞歸合并往上走
$right = mergeSort($right); // 右邊拆分完畢開始遞歸往上走
$arr = merge($left, $right); // 合并兩個數組,繼續遞歸
return $arr;
}
// merge函數將指定的兩個有序數組(arrA, arr)合并并且排序
function merge($arrA, $arrB) {
$arrC = array();
while (count($arrA) && count($arrB)) {
// 這里不斷的判斷哪個值小, 就將小的值給到arrC, 但是到最后肯定要剩下幾個值,
// 不是剩下arrA里面的就是剩下arrB里面的而且這幾個有序的值, 肯定比arrC里面所有的值都大所以使用
$arrC[] = $arrA[0] < $arrB[0] ? array_shift($arrA) : array_shift($arrB);
}
return array_merge($arrC, $arrA, $arrB);
}
測試:
$startTime = microtime(1);
$arr = range(1, 10);
shuffle($arr);
echo "before sort: ", implode(", ", $arr), "
";
$sortArr = mergeSort($arr);
echo "after sort: ", implode(", ", $sortArr), "
";
echo "use time: ", microtime(1) - $startTime, "s
";
時間復雜度
歸并排序的時間復雜度是 O(N*lgN)。
假設被排序的數列中有 N 個數。遍歷一趟的時間復雜度是 O(N)，需要遍歷多少次呢？
歸并排序的形式就是一棵二叉樹，它需要遍歷的次數就是二叉樹的深度，而根據完全二叉樹的可以得出它的時間復雜度是 O(N*lgN)。
參考資料歸并排序
十大經典排序算法動畫與解析
感謝您的閱讀，覺得內容不錯，點個贊吧
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/30108.html
摘要：良好的排序算法具有進行最少的比較和交換的特征。冒泡排序是一個基于比較的排序算法，被認為是效率最低的排序算法之一?，F在讓我們使用實現冒泡排序算法。插入排序到目前為止，我們已經看到了兩種基于比較的排序算法。 預警 本文適合對于排序算法不太了解的新手同學觀看，大佬直接忽略即可。因為考慮到連貫性，所以篇幅較長。老鐵們看完需要大概一個小時，但是從入門到完全理解可能需要10個小時(哈哈哈，以我自己...
摘要：數據結構常見數據結構數組是最簡單而且應用最廣泛的數據結構特征使用連續內存空間來存儲存放相同類型或著衍生類型的元素數組比較特別，可以存放八種數據類型通過下標來訪問集合特征保存不重復的元素字典特征就是關聯數組，以形式存儲棧，與隊列相似特征存儲數 數據結構 常見數據結構 Array 數組是 最簡單 而且 應用最廣泛 的數據結構 特征： 1、使用連續內存空間來存儲 2、存放相同類型或著衍生類型...
摘要：兩個單元素數組的合并實際就是對這兩個數進行了排序，即變為，同樣再對后一組的兩個數歸并排序，即變為，再將兩單元數組歸并成四單元數組即和歸并為。 前言 本周講解兩個50多年前發明，但今天仍然很重要的經典算法 (歸并排序和快速排序) 之一 -- 歸并排序，幾乎每個軟件系統中都可以找到其中一個或兩個的實現，并研究這些經典方法的新變革。我們的涉及范圍從數學模型中解釋為什么這些方法有效到使這些算法...
摘要：常見的內部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數排序等。用一張圖概括歸并排序英語，或，是創建在歸并操作上的一種有效的排序算法，效率為。 常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。用一張圖概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...
閱讀 2038·2021-10-08 10:05
閱讀 1882·2021-09-22 15:31
閱讀 3003·2021-09-22 15:13
閱讀 3478·2021-09-09 09:34
閱讀 2072·2021-09-03 10:46
閱讀 3112·2019-08-30 15:56
閱讀 1697·2019-08-30 15:53
閱讀 2351·2019-08-30 15:44
