【圖解數據結構】 一組動畫徹底理解歸併排序

• 2019 年 11 月 13 日
• 筆記

授權轉載自五分鐘學算法，轉載聯繫出處~

由於LeetCode上的算法題很多涉及到一些基礎的數據結構，為了更好的理解後續更新的一些複雜題目的動畫，推出一個新系列 —–《圖解數據結構》，主要使用動畫來描述常見的數據結構和算法。本系列包括十大排序、堆、隊列、樹、並查集、圖等等大概幾十篇。

歸併排序

歸併排序（Merge sort）是建立在歸併操作上的一種有效的排序算法。該算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

作為一種典型的分而治之思想的算法應用，歸併排序的實現由兩種方法：

• 自上而下的遞歸（所有遞歸的方法都可以用迭代重寫，所以就有了第 2 種方法）；
• 自下而上的迭代；

和選擇排序一樣，歸併排序的性能不受輸入數據的影響，但表現比選擇排序好的多，因為始終都是 O(nlogn) 的時間複雜度。代價是需要額外的內存空間。

算法步驟

1. 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合併後的序列；
2. 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；
3. 比較兩個指針所指向的元素，選擇相對小的元素放入到合併空間，並移動指針到下一位置；
4. 重複步驟 3 直到某一指針達到序列尾；
5. 將另一序列剩下的所有元素直接複製到合併序列尾。

來源：https://github.com/hustcc/JS-Sorting-Algorithm

算法演示

動畫演示加載有點慢，請稍等片刻

排序動畫過程解釋

1. 首先，將數字分割成兩片區域
2. 再將數字分割成兩片區域
3. 依次劃分
4. 直到每片區域只有一個元素
5. 分割完成
6. 接下來，將分割的每片區域進行合併組合
7. 合併時，按照數字的升序移動，使得合併後的數字在組內按升序排列
8. 當合併包含多個數字的組時，比較開頭的數字，移動其中較小的數字
9. 比如在動畫中，比較開頭的 4 和 3
10. 其中 4 大於 3， 因此移動 3
11. 按照同樣的邏輯去比較該列剩餘的頭數
12. 4 小於 7 ，所以移動 4
13. 同樣的邏輯去進行接下來的操作
14. 遞歸的重複組的合併操作，直到所有數字都在一個組中。
15. 完成 歸併排序

代碼實現

為了更好的讓讀者用自己熟悉的編程語言來理解動畫，筆者將貼出多種編程語言的參考代碼，代碼全部來源於網上。

C++代碼實現

Java代碼實現

Python代碼實現

JavaScript代碼實現

如果你是iOS開發者，可以在GitHub上 https://github.com/MisterBooo/Play-With-Sort-OC 獲取更直觀可調試運行的源碼。

這麼硬的乾貨，不給個好看？！