Aloha！又是我少女人妻終於來到第 15 天了～不知不覺就過了一半了，大家有聽過跑者愉悅理論嗎，就是很多事情再堅持一下，突破撞牆期後會突然有滿滿能量湧現，所以凡事都要告訴自己再堅持一下下，那種厭煩與疲憊的感受很快就會消散的！阿不過我通常累了就去睡覺了哈哈哈哈哈哈！

常見的排序演算法

昨天提到了氣泡排序、選擇排序以及插入排序，今天要繼續提及其他的排序法摟～

堆積排序 Heap Sort

堆積排序是利用堆積樹的性質來做排序，堆積資料結構請參考文章：資料結構：堆積 Heap 中的說明。

一開始先將數列儲存在堆積中

從根節點取出元素

重新調整堆積，再從根節點取出元素

再重新調整堆積，再從根節點取出元素

一直反覆操作直到所有元素都排列完成～

合併排序 Merge Sort

合併排序是將數列分割為左右兩個幾乎等長的數列，之後再分割，直到不可分割為止，再依序比對並合併。

將未排序數列盡量分為兩組 (如黃色底線所示)

劃分後的數列再進行劃分 (如粉色底線所示)

這時元素 5 跟 3 還能再進行劃分 (如藍色底線所示)

無法再劃分後開始將元素合併，先從最左方、最下層開始合併，合併時比較兩元素的大小，並做排序。

較小的數排前方，此時 3 < 5 ，所以 3 排在前方

再比較左方兩數列的第一個數，此時是 1 < 3

所以先取 1 排前方，再取 3 ，最後取 5

再將 2 、 4 依照上述方式比較後合併，最後得到兩數列

再比較兩數列第一個值，因 1 < 2 ，所以 1 先排入 1 ，其次為 2

同理比較 3 跟 4，並做合併，最後排入 5

當啷～然後排序就完成了～

快速排序

快速排序是從數列中隨機選擇一個基準值，將小於基準的數排在基準值的左邊，大於基準值的數在右邊，被基準值分割的兩數列再用上述的方式重複執行並排序，直到排序完成為止。

取一組未排序的元素數列，並隨機取一個元素當基準點，下圖選擇 3 為基準點

將小於基準值的元素排左邊，大於基準值的元素排右邊

因 5 > 3 ，所以 5 排在 3 的右邊

因 1 < 3 ，所以 1 排在 3 的左邊

同理，2 排在 3 的左邊，4 排在右邊

但此時，基準點 3 的左邊是未排序的數列

所以在未排序的數列中，再隨機取一值為基準點，下圖取 2 為基準點，因為 1 < 2 ，所以 1 要排在基準點 2 的左邊。

基準點 3 的右邊也是未排序的數列

隨機取基準點為 5 ，因 4 < 5 ，所以 4 排在基準點 5 的左邊

最後確定所有基準點左右都排序完成後，排序就結束了～

參考資料:

演算法筆記:Sort
[演算法] 排序演算法(Sort Algorithm)

好的～今天就先到這邊啦！大家夢裡見～還有明天見～掰掰～～