Aloha～！又是我少女人妻 Uerica！今天終於可以進入到演算法的章節啦 (歡呼) ～ 之前因為從沒碰過演算法，在整理和學習的時候發現大家都從資料結構開始提及，當時我就想那資料結構應該很重要吧～於是花了幾天時間認真研究資料結構，直到前兩天我跟老公說，怎麼辦文章都寫快一半了還沒寫到演算法...老公用不失禮貌的微笑看著我並對我說：難怪妳在廚房想了 30 天都想不出來。Q_Q

好的今天要來提排序 sort 啦～

排序 sort

排序簡單來說就是將資料由大到小，或由小到大順序排列。平常上網購物時會看到可依照價錢由高至低排序商品的按鈕，或依照上架日期由新至舊陳列商品等，或是生活上在學校老師依成績高低排列，在親戚家跟表堂兄弟們排列身高等（我永遠都是最矮的那個，時間複雜度 O(1) QQ）。排序後的優點是資料或物件更容易閱讀、統計分析、快速搜尋等。

排序演算法分類

內部與外部排序法

• 內部排序 Internal sort : 資料量少，在主記憶體(RAM)就可以完成，一般的演算法都是屬於內部排序。
• 外部排序 External Sort : 資料量較大，需透過其它儲存裝置 (Disk, File) 輔助，外部排序通常會分次載入部份的資料到記憶體，用內部排序演算法排序後再回存或合併結果

穩定與不穩定排序法

• 穩定排序法 stable sorting : 相同的值排序前後順序皆相同
• 不穩定排序法 unstable sorting : 相同的值排序前後順序可能會對調

簡單與高等排序法

• 簡單排序法 : 排序演算法簡單，但執行時間較長。
• 高等排序法 : 排序演算法複雜，執行時間較短。

常見的排序演算法

排序演算法的簡要比較，來自維基百科

氣泡排序 bubble sort

氣泡排序法是利用反覆進行相鄰的兩個值兩兩比對，若順序錯誤就進行交換。因移動時最小的數很像水中的氣泡慢慢浮到數列頂端所以稱為氣泡排序，也稱泡沫排序法。以下例圖為從右到左比較，也有看到有人從左到右比較，不過概念都相同，只是程式寫法會有些差異。

假設現在有一堆亂序數列要由小至大做排序

先比較 4 跟 2 ，因 4 的值較大所以維持不變

再往前比較 2 跟 1，2 的值較大所以也維持不變

再往前比較 1 跟 ３

喔這時發現 1 的值比 3 小！

所以將 1 跟 3 的位置做交換

交換完成後，再向前比較，這次是比較 1 跟 5

因為 1 的值比較小，所以跟 5 交換

這時第一輪的排序就結束了，可以發現數列中的最小值 1 已經排到數列的最前面了～

剩餘的亂序數列再從頭開始比較，跟剛剛一樣先比較 4 跟 2，因為 4 比較大所以維持不變

再比較 2 跟 3，此時 2 比 3 小，所以跟 3 做交換

再比較 2 跟 5 ，因 2 比 5 小，所以與 5 做交換

這時 2 已經到數列的正確位置，排序第二輪就結束了

後面未排序的數列如同上述一樣，再重新比對與交換，直到所有值符合由小到大排序，就算排序完成。

選擇排序 selection Sort

選擇排序法是找出數列中的最大或最小值，並與數列起始位置的值交換，反覆操作直到排序完成為止。

來用選擇排序排跟剛剛一樣的亂數

先找出數列中的最小值，這邊找到是 1

讓最小值 1 直接跟最前方的數值交換

如此一來，第一輪的排序就完成了。

再從為排序的值中找最小值，於是找到最小值是 2

讓 2 與最前方的為排序的數值做交換

於是第二輪也結束了，1 跟 2 都排序好了～

跟剛剛一樣，再從為排序的值找最小值，這邊找到是 3

3 再跟最前方未排序的數值做交換

第三輪結束

再找未排序的最小值

做交換

然後將啷～排序就完成啦～選擇排序法很簡單吧！

插入排序 Insertion Sort

插入排序是依序將未排序的資料一一由後向前掃描，並將數插入至對應的位置。

跟剛剛一樣的亂數～

第一個值先定位，第一輪就算完成了

再來由未排序的值 3 來往前比較

因 5 大於 3 ，所以兩個位置需交換

換到左邊沒有大於自己的數值為止，第二輪結束

再來由未排序的 1 來做排序

因為 5 大於 1，所以交換

1 再往前比較，3 也大於 1，所以再交換

換到直到左邊沒有大於自己的數值為止，第三輪就結束了～

之後以此類推，直到所有直排序完成～

參考資料:
演算法筆記:Sort
[演算法] 排序演算法(Sort Algorithm)

好的～今天就先到這邊啦！抱持一個凡事先求有再求好的心態，哈哈哈，我要先去遛狗了明天見掰掰～