【前情提要】 【演算法】排序演算法 Sorting Algorithm 【演算法】插入排序與希爾排序 Insertion & Shell Sort Ok , 那今天就接續前兩篇把最後三個排序演算法給講完。 一、選擇排序 Selection Sort
選擇排序可以說是最簡單、最直觀的排序演算法了,如果說有天你什麼排序演算法都忘光光了,突然又要你做排序,那麼你很有可能就會下意識的使出選擇排序 ( 這東西簡單到都像反射動作了xD )。
它演算法的概念很簡單,一個一個檢查未排序的資料,找最小(或最大)的從頭開始排,如此重複執行到結束。 看完下面這張 Gif 你們大概就懂了。 二、合併排序 Merge Sort
Merge Sort 一般稱作合併排序,但也有人叫作「歸併排序」,它呢跟 Jason 之前介紹的快速排序(Quick Sort) 很像,都是採用演算法中分治法 Divide and conquer 的方式來解決排序問題。
而它跟快排最大的不同就是,在拆解成子問題的時候,它會把數列拆解分割到只有一個元素(Element):
在做完分割 ( partition ) 拆解成子問題 ( divide ) 的動作以後,
再來要做的就是解決子問題 ( conquer ): 歸併、合併 ( merge ) 。
而 Merge 兩個已排序的子數列這部分的邏輯很簡單,跟一般在資料結構中做合併的方法是一樣的。
【程式碼下載】 三、堆積排序 Heap Sort
其實所謂的堆積排序法,你可以把它想像成上面提到的選擇排序改良版。
利用在資料結構中二元樹的堆積樹來做資料排序,以改善選擇排序需要做的執行次數。 其中堆積樹又區分為 Max-heap、Min-heap、Min-max heap 及 Deap 四種,一般我們要做 heap sort 的時候拿Max-heap 或 Min-heap 來用就可以了 ( 取決於你想要從大排到小,還是從小排到大 )。想要了解這個演算法,首先我們得來看一下,要如何將一顆二元樹 ( Binary tree ) 轉換成一顆堆積樹:
上圖範例中的二元樹是由 Input { 5,2,4,8,7,6,3,1 } 依次將元素加入產生的。
這邊要注意到的是 一顆 Heap Tree 不會是唯一,因為只要父節點大於子節點就可以了。
Ok, 假設我們今天已經得到一顆 Max-heap tree 如上圖好了,那我們又該如何用這東西來做排序呢?
首先你可以發現 max-heap tree 有一個最大的特性就是它 root [0] 永遠會是最大的! 所以我們只要把 root 節點的資料移到已排序的陣列,然後而一顆 heap tree 在它節點被移除後, 會自動的用最後一個節點 [7] 來補上被移除的節點,接著做一個Heapify 的動作。 而 Heapify 其實就和上面把 Binary Tree 轉成 Max-heap Tree 的過程很像,就是在確保父節點大於子節點。
1 評論
Ceylan
6/8/2020 09:57:36
I was looking for a good selection sort animation for my students. Thank you.
回覆
發表回覆。 |
Jason Chen人不光是生來就擁有一切,而是靠他從學習中得到的一切來造就自己。- 歌德 文章分類
全部
封存檔
九月 2023
|