AppWorks School
Published in

AppWorks School

初學者學演算法|排序法進階:合併排序法

程式麻瓜的程式知識課(六)

Source: https://burst.shopify.com/photos/laptops-at-workstations-coding

初學者學演算法系列的第一篇文章中,我們認識了演算法這個玩意兒,也對評斷演算法好壞的工具「時間複雜度」有了基本的概念。在上一篇文章中,我們了解了經典的演算法入門:排序法。並從最簡單的排序法選擇排序 (Selection Sort) 與插入排序 (Insertion Sort) 開始學習。

瞭解了兩個 O(n) 複雜度的排序法後,讓我們來嘗試改善排序法的效率,從 O(n²) 到 O(n log n),學習更進階的排序法。

目錄:常見的六種時間複雜度與演算法

  1. O(1):陣列讀取
  2. O(n):簡易搜尋
  3. O(log n):二分搜尋
  4. O(n²):選擇排序法、插入排序法
  5. O(n logn):合併排序法
  6. O(2^n):費波那契數列

O(n logn):合併排序 (Merge Sort)

時間複雜度為 O(n log n) 的演算法,代表著執行時間會隨著以二為底的 log n 再乘上 n 成長。最常見的例子是合併排序法 (Merge Sort) 與快速排序法 (Quick Sort),而本篇文章將以新手比較好掌握的合併排序法為例。

合併排序法

相對於選擇排序法,合併排序法屬於比較進階的演算法,排序方法也比較複雜一點,基本的步驟可以分為「拆分」與「合併」:

拆分

  1. 把大陣列切一半成為兩個小陣列
  2. 把切好的兩個小陣列再各自切一半
  3. 重複步驟二直到每個小陣列都只剩一個元素

合併

  1. 排序兩個只剩一個元素的小陣列並合併
  2. 把兩邊排序好的小陣列合併並排序成一個陣列
  3. 重複步驟二直到所有小陣列都合併成一個大陣列

現在,讓我們再次出動熟悉的數列 [41, 33, 17, 80, 61, 5, 55] 當作例子來說明:

在圖中的上半部,我們將未排序的陣列對半切,直到每個小陣列都只剩一個元素;而在圖中的下半部,我們將被對半切開的小陣列兩兩合併與排序。

因為兩個小陣列在合併前都各自排序好了(只有一個元素的陣列也視為已排序),所以在合併兩個排序好的陣列時,我們只需要不斷比較兩邊的第一個元素,把比較小的丟到新的大陣列,就能完成排序。

接下來,讓我們用慢動作再複習一次:

https://commons.wikimedia.org/wiki/File:Merge-sort-example-300px.gif

接下來,我們會一邊分析合併排序的時間複雜度,一邊再進一步用圖拆解合併的步驟是如何進行。

合併排序的時間複雜度

為了分析時間複雜度,我們同樣將合併排序的步驟分為拆分與合併討論。

拆分

拆分屬於簡單的步驟,從上面的圖就可以觀察,把一個 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

Want to Learn More? Weekly I/O!

Weekly I/O is a project where I share my learning Input/Output. Every Sunday, I write an email newsletter with five things I discovered and learned that week.

Sign up here and let me share a curated list of learning Input/Output with you 🎉

--

--

--

AppWorks School 由 AppWorks 於 2016 年成立,專注於新時代數位人才教育,提供想投入網路與電商的新鮮人、轉職青年,一個與業界高度整合的培訓計畫。

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Cheng-Wei Hu | 胡程維

Cheng-Wei Hu | 胡程維

Voracious learner | Software developer | Cornell Tech student | Better Medium Stats: bit.ly/2RH8Jsf | Medium Articles List: chengweihu.com/blog

More from Medium

Photo Filtering API: How to Emboss an Image with Java

Java 11 - 1Z0-819 : A Personal Feedback

Serial Port programming Tutorial using Java SE for Embedded Developers

02. A Trip to Objectville