擁抱「資料結構」的「演算法」(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 )

昨日謎題

謎題說明：練習使用某一條件將資料分成兩堆，找出不具有對稱特質的字母被刪除，具有對稱特質的字母會被留下來，F、D、P、G、I、Q、J、V、I、D、R、Z、E，整理一下，就會得到 DIVIDE，就是快速排序採用的分而治之法(Divide-and-conquer)，你答對了嗎？

留言

張貼留言

這個網誌中的熱門文章

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

以下是自己的 CPE 一顆星選集 解題紀錄 (共有 49 題) 每次考試都會從一顆星選集中抽 1 提出來考 算是比較能把握的部分，重點筆記整理如下 內容包含題目說明、程式碼、註解說明、解答、考古題統計(下方土黃色日期) 解題使用的程式語言是  JAVA  目前有提供 10 題的試閱 另有提供完整 49 題的完整解答 ( pdf 檔 )， 共 305 頁， 售價 $399 元 ， 若有需要請來信購買 greens2314@gmail.com 推薦閱讀： 建議熟讀 java 基本觀念，與使用 eclipse 練習， 等熟悉之後再到瘋狂程設考試(一定要懂如何查 JAVA API 與使用英漢字典) Java 考試常用的方法或類別 Eclipse 常用小技巧 CPE 一顆星選集： 編號 | 題目名稱 | 歷屆考古題日期 1. Vito's family (CPE10406, UVA10041) 2024/04/23 可與第 40 題一起看 2. Hashmat the brave warrior (CPE10407, UVA10055) 3. Primary Arithmetic (CPE10404, UVA10035) 　 2011/05/25、2023/03/21 4. The 3n + 1 problem (CPE10400, UVA100) 　 2010/06/09 5. You can say 11 (CPE10460, UVA10929) 　 2011/12/20 6. Bangla Numbers (CPE10414, UVA10101) 　 2018/12/18 7. List of Conquests (CPE21924, UVA10420) 　 2019/03/26 　　可與 第 8, 11, 43 題一起看 字元與字串 8. What's Cryptanalysis? (CPE10402, UVA10008) 　　可與 第 7, 11, 43 題一起看 9. Decode the Mad man (CPE10425, UVA10222) 　 2021/10/19 10. Problem J: Summing Digits (CPE10473, UVA11332) ...
Read more »

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

圖片
在團隊開發過程中，什麼時候是程式碼瘋狂修改的階段呢， 無非就是Code Review了，有時候卡個幾天或是幾個月都是有可能的， 裡面常出現的comment，每次幾乎都會出現的就是排版的問題， 例如空白多一個少一個，括號還沒換行等等的小瑕疵， 對於心思不夠細膩的人而言，真的十分的惱人 團隊中喜歡將大括號換行， 例如： if(true) {   //code } else {   //code } 那也許有些團隊喜歡： if(true){   //code }else{   //code } 有時候不只括號要不要換行，連else要不要換行都有各自的喜好， 所以有時候要統一使用團隊規定的喜好真的會有眼殘的時候， 自己檢查老半天可能還是有漏網之魚， 但現在不用擔心啦！ 只要使用Format 格式化文件就能為你分憂解勞， 設定方式如下： 編輯 > 進階 > 格式化文件 Visual Studio會根據你的環境設定幫你自動重新排版 設定方式如下： 工具 > 選項 切換到 文字編輯器 > C# >程式碼樣式 > 格式化 > 新行 這邊可以設定很多換行的邏輯， 將對應的項目打勾跟取消勾選，下面的黑色區域會顯示排版的格式， 可根據自己或是團隊的喜好去做調整，即可自動排出你想要的格式囉！ 如果覺得 編輯 > 進階 > 格式化文件 這個選項太難找到， 可以參考這篇文章，將他加入在明顯的工具列區域喔 http://greens2314.blogspot.tw/2017/09/visual-studio-2015.html
Read more »

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

圖片
    👉   CPE 一顆星選集列表(49題) 題目說明與解答 題目 Vito 在紐約有非常多的親戚，他希望在紐約找到一間房子，這間房子到每個親戚家的距離總和，要是最少的距離 輸入說明 輸入資料包含很多筆測試資料 每筆測資，包含親戚數量與每位親戚家的街號 親戚數量介於1~499、街道範圍介於1~29999 多位親戚可住在同一條街 輸出說明 針對每筆測試資料，計算出 Vito 到每位親戚家的最短距離總和 街與街的距離 = 街道數字相減取絕對值 解題技巧 中位數 是指一組數字的中間數字；即是有一半數字的值大於中位數，而另一半數字的值小於中位數，其意義是在所有資料中居於中間位置的代表 排序 街道的數字同時代表距離，透過排序，可得知中位數 解題過程 取得輸入 取得資料筆數 根據資料筆數取得親戚數量 根據親戚數量取得街道編號 將街道編號存入陣列中 將親戚的街道位置 由小至大 排序 呼叫 Arrays 類別提供的 sort() 方法 https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html 假設親戚有 5 位，分別住在：2、5、8、4、2街 排序後為：2 、2、4、5、8街 計算中位數 中位數在陣列中的索引 = 親戚數量 / 2 假設親戚有 5 位( 奇數) ，分別住在：2、5、8、4、2街 排序後為：2 、2、4、5、8街，其中 4 為中位數，中位數有 1 個 5位親戚 / 2 = 2.5，取整數，陣列索引 2 的位置，儲存的是第 4 街 假設親戚有 4位 (偶數) ，分別住在：2、5、8、4街 排序後為：2 、4、5、8街，其中 4 或 5 為中位數， 中位數有 2 個，擇一即可 4位親戚 / 2 = 2，陣列索引 2 的位置，儲存的是 5 街 計算最小距離總和並印出 宣告 sum 變數，統計距離 使用 foreach 將各街道編號 減掉 中位數編號，取絕對值並進行家總 取絕對值要呼叫  Math.abs ()  方法 奇數情況 ： 中位數有 1 個 假設親戚有 5 位   ，分別住在： 2 、2、 4 、5、8 街 中位數 4 ，Vito 住在 4 街，到其他親戚家的距離總和即是最小值 9   偶數情況 ： ...
Read more »