擁抱「資料結構」的「演算法」(22) - 合併排序法

 

前言

合併排序法顧名思義就是會有合併的動作,在合併之前想必應該會有切割的動作,一起來看看這這分分合合的演算法吧XD


生活常識

你有用切水果的經驗嗎?通常我們都習慣將一顆水果對半切,因為一整顆的水果比較不容易直皆整顆嗑,例如:西瓜XD,在對半切再對半切至小塊之後,就很容易不知不覺吃掉半顆,最後通通在肚子裡面集合了XD


圖片來源:https://www.pexels.com/zh-tw/photo/952480/

對半的這個概念,也很像有些店家的手工麵的製作過程,會看到師傅把麵團甩成麵條,過程中不斷的對折再對折,最後在剪斷就會變成可以下鍋煮的麵了


圖片來源:https://www.pexels.com/zh-tw/photo/3771814/

這樣一路分之後,會發生什麼事呢?就像三國演義裡面有這麼一句話:「天下大勢,分久必合,合久必分。」,其中的分久必合很有合併排序演算法的味道,分裂完之後,就會開始統一


圖片來源:https://www.books.com.tw/products/0010854705?sloc=main

團康遊戲中的「我是拳王」,就是在活動一開始,每一個人為一個單位,去找另一個人猜拳,如果猜輸,輸的人就要搭著猜贏者的肩膀成為他的隊友,如果猜贏,則可繼續找人猜拳,猜著猜著隊伍的人數會越來越多,最後剩下兩個隊伍時最刺激,因為猜贏者就是最大的勝利者,所有人都要排勝利者的後面,從此活動可以觀察出,從一開始一個人為單位,最後會合併成一大群人



專業知識 - 合併排序法 Merge Sort

合併演算法會將資料對切為兩個部分,然後再將左半邊與右半邊繼續再切一半,切到最小單位,也就是只剩下一個數值,已無法再被切割為止,然後再進行小單位之間整合,再到大單位之間的整合,最後將全部資料都排序好

分割

  1. 取得資料長度,除以 2 之後, 將資料分為兩個區塊
    例如:有一陣列資料為:3, 8, 1, 7, 4, 2, 6, 5,共 8 個資料,除以 2 ,陣列會被分割為 2 個陣列 3, 8, 1, 7 與 4, 2, 6, 5,各自的長度為 4

  2. 重覆第 1 個步驟,再將資料,除以 2 之後, 將資料分為兩個區塊
    例如:
    3, 8, 1, 7 會被分割為 2 個陣列,長度為 2 :3, 8 與 1, 7
    4, 2, 6, 5 會被分割為 2 個陣列,長度為 2 :4, 2 與 6, 5

  3. 繼續重覆第 1 個步驟,直到陣列長度為 1 則可停止,表示已經完成分割動作
    例如:
    3, 8 會被分割為 2 個陣列,長度為 1 :3 與 8
    1, 7 會被分割為 2 個陣列,長度為 1 :1 與 7
    4, 2 會被分割為 2 個陣列,長度為 1 :4 與 2
    6, 5 會被分割為 2 個陣列,長度為 1 :6 與 5


合併

將目前最小單位的陣列兩兩合併,直到合併成一個大陣列為止

  1. 選取兩個長度為 1 的陣列,取第一個值進行排序
    例如:
    3 與 8 ,由小到大排序之後,將兩個長度為 1 的陣列合併成長度為 2 的陣列:3, 8
    1 與 7 ,由小到大排序之後,將兩個長度為 1 的陣列合併成長度為 2 的陣列:1, 7
    4 與 2 ,由小到大排序之後,將兩個長度為 1 的陣列合併成長度為 2 的陣列:2, 4
    6 與 5 ,由小到大排序之後,將兩個長度為 1 的陣列合併成長度為 2 的陣列:5, 6

  2. 選取兩個長度為 2 的陣列,取第一個值進行排序
    例如:
    3, 8 與 1, 7,由小到大排序之後,將兩個長度為 2 的陣列合併成長度為 4 的陣列: 1, 3, 7, 8
    2, 4 與 5, 6,由小到大排序之後,將兩個長度為 2 的陣列合併成長度為 4 的陣列: 2, 4, 5, 6



  3. 選取兩個長度為 4 的陣列,取第一個值進行排序
    例如:
    1, 3, 7, 8 與 2, 4, 5, 6,將兩個長度為 4 的陣列合併成長度為 8 的陣列:1 ,2, 3, 4, 5, 6, 7, 8



分析

  • 最壞的情況與最好的情況
    合併時需考慮此層級中有多少個數值,取最前面的數值互相比較之後才能決定排序,所以如果數值有 n 個,執行的時間就是 O(n),另外因為不斷的對半切,會得到 log n 層,所以處理全部層級的時間為 O(n log n)

今日小結

合併排序法,就是分割至最小單位之後,兩兩比較排序並合併成較大的單位,再挑選兩個較大單位繼續兩兩比較,再排序並合併成更大的單位,直到最大單位出現即排序完成


今日謎題

演奏會持續進行,在中場休息時間,舉辦了一個有講徵答活動,題目裡面有一堆數字:4, 2, 3, 4, 5, 3, 4, 5,這些數字看起來似乎是一首歌的旋律,答案是等一下即將演奏的歌曲中某兩個小節,會由中西合併的樂手一起演奏,你能從推算過程中觀察出下一首要演奏的歌曲嗎?( 數字由小至大排列請將數字填入問號處,歌曲每小節有4拍,共四節,提示:5531 ???? ???? 5353 )

昨日謎題

謎題說明:練習使用某一條件將資料分成兩堆,找出不具有對稱特質的字母被刪除,具有對稱特質的字母會被留下來,FDPGIQJVIDRZE,整理一下,就會得到 DIVIDE,就是快速排序採用的分而治之法(Divide-and-conquer),你答對了嗎?

留言

這個網誌中的熱門文章

CPE 一顆星選集題目說明與解答 - Java 筆記與心得分享

Visual Studio 自動排版格式化程式碼

1. Vito's family (CPE10406, UVA10041) - CPE一顆星解答與說明