初學者學演算法｜排序法進階：合併排序法
程式麻瓜的程式知識課（六）
在初學者學演算法系列的第一篇文章中，我們認識了演算法這個玩意兒，也對評斷演算法好壞的工具「時間複雜度」有了基本的概念。在上一篇文章中，我們了解了經典的演算法入門：排序法。並從最簡單的排序法選擇排序 (Selection Sort) 與插入排序 (Insertion Sort) 開始學習。
瞭解了兩個 O(n) 複雜度的排序法後，讓我們來嘗試改善排序法的效率，從 O(n²) 到 O(n log n)，學習更進階的排序法。
目錄：常見的六種時間複雜度與演算法
- O(1)：陣列讀取
- O(n)：簡易搜尋
- O(log n)：二分搜尋
- O(n²)：選擇排序法、插入排序法
- O(n logn)：合併排序法
- O(2^n)：費波那契數列
O(n logn)：合併排序 (Merge Sort)
時間複雜度為 O(n log n) 的演算法，代表著執行時間會隨著以二為底的 log n 再乘上 n 成長。最常見的例子是合併排序法 (Merge Sort) 與快速排序法 (Quick Sort)，而本篇文章將以新手比較好掌握的合併排序法為例。
合併排序法
相對於選擇排序法，合併排序法屬於比較進階的演算法，排序方法也比較複雜一點，基本的步驟可以分為「拆分」與「合併」：
拆分
- 把大陣列切一半成為兩個小陣列
- 把切好的兩個小陣列再各自切一半
- 重複步驟二直到每個小陣列都只剩一個元素
合併
- 排序兩個只剩一個元素的小陣列並合併
- 把兩邊排序好的小陣列合併並排序成一個陣列
- 重複步驟二直到所有小陣列都合併成一個大陣列
現在，讓我們再次出動熟悉的數列 [41, 33, 17, 80, 61, 5, 55] 當作例子來說明：
在圖中的上半部，我們將未排序的陣列對半切，直到每個小陣列都只剩一個元素；而在圖中的下半部，我們將被對半切開的小陣列兩兩合併與排序。
因為兩個小陣列在合併前都各自排序好了（只有一個元素的陣列也視為已排序），所以在合併兩個排序好的陣列時，我們只需要不斷比較兩邊的第一個元素，把比較小的丟到新的大陣列，就能完成排序。
接下來，讓我們用慢動作再複習一次：
接下來，我們會一邊分析合併排序的時間複雜度，一邊再進一步用圖拆解合併的步驟是如何進行。
合併排序的時間複雜度
為了分析時間複雜度，我們同樣將合併排序的步驟分為拆分與合併討論。
拆分
拆分屬於簡單的步驟，從上面的圖就可以觀察，把一個 n 的陣列切切切，切到每個小陣列都只有 1 個數字時，需要 n-1 個步驟（切 n-1 刀）。
合併
合併屬於比較複雜一點的步驟，因為在合併的過程中我們同時也要完成排序。
把兩個排序好的小陣列合併成一個排序好的大陣列需要多少步驟呢？在上圖的每次排序中，如果兩個小陣列加起來有 n 個數字，總共就需要 n 個步驟。讓我們用上圖中的最後一次排序做為示範：
從上面的圖可以看到，在合併兩個已經排序好的小陣列時，我們每次都只需要比較兩個陣列的第一個數字，把比較小的依序丟到新的陣列中，再重新比較兩個小陣列的第一個數字。觀察上面的結果，要合併 n 個數字時，我們剛好也只需要 n 個步驟。
那在合併排序法中，我們總共需要進行幾回合這樣的合併呢？在上面的例子中，從一開始 7 個小陣列合併成 4 個，再從 4 個合併成 2 個，最後合併成 1 個，因為每一回合的合併，都可以讓下一回合需要合併的陣列減少一半，這樣的特性表示總共需要合併的回合數會是以 2 為底的 log n 次。
- 每回合的合併需要花：O(n)
- 總共需要回合數：O(log n)
結合拆分與合併
拆分的步驟數為 n-1，合併的步驟數為 n 乘上 log n，相加後我們可以得知合併排序法總共的步驟數為 n-1 + n log n。化成大 O 符號時，我們只計最高項係數並省略常數，因此我們終於得到合併排序法的時間複雜度，即為 O( n log n)。
合併排序法在程式碼中的例子，可以說是讓很多新手卡關的地方。合併排序法在實作時，運用到了「遞迴」這個比較進階的觀念，我們在下一篇用費氏數列的例子來簡單解釋。如果想要挑戰看看，也可以先練習自己寫寫看要怎麼把上面的想法實作出來哦！
def Merge_Sort(array):
if len(array) > 1:
mid = len(array) // 2
left_array = array[:mid]
right_array = array[mid:]
Merge_Sort(left_array)
Merge_Sort(right_array)
right_index = 0;
left_index = 0;
merged_index = 0;
while right_index < len(right_array) and left_index < len(left_array):
if(right_array[right_index] < left_array[left_index]):
array[merged_index] = right_array[right_index]
right_index = right_index + 1
else:
array[merged_index] = left_array[left_index]
left_index = left_index + 1
merged_index = merged_index + 1
while right_index < len(right_array):
array[merged_index] = right_array[right_index]
right_index = right_index + 1
merged_index = merged_index + 1
while left_index < len(left_array):
array[merged_index] = left_array[left_index]
left_index = left_index + 1
merged_index = merged_index + 1
Numbers = [41, 33, 17, 80, 61, 5, 55]
Merge_Sort(Numbers)
print(Numbers)小結
在這篇文章中，我們了解了進階的排序法：合併排序。合併排序是較為快速的排序法，每次的步驟是先把陣列切一半，分別排序兩邊，再把兩邊排序好的陣列合併起來，總共需要的時間複雜度是 O(n log n)。
在下一篇文章中，我們將進階到最耗時的時間複雜度 O(2^n)，並介紹其代表的時間複雜度：費氏數列遞迴解法。
想要準時收看新文章嗎？快追蹤 AppWorks School 的粉專與 Medium Publication 吧！
【AppWorks School Batch #12 限時招生中】
AppWorks School 將開設 Android、iOS、Front-End 與 Backend Class 四個不同技能的訓練班次，全程免費，透過線上學習 4 週，駐點集訓 16 週的專案導向訓練，幫助你成為軟體工程師。
歡迎想成為軟體工程師的朋友，把握機會申請，報名到 7/22 23:59 截止喔！～https://bit.ly/2BUQmvn
嗨，我是程維，目前在美國 Google 擔任軟體工程師。如果你對入門機器學習、深度學習、人工智慧和大語言模型有興趣，我目前在準備一系列入門的文章。歡迎在這個網頁表單輸入你的電子信箱，我會在寫好的第一時間將文章寄送給你。
