資料結構與演算法筆記 - Sort (排序) 介紹
在寫程式常常會用到的演算法，我相信大部分都是 Sort (排序) 類型的，今天這篇文章介紹在 Sort 世界裡面有什麼重點是我們可以牢記的。
這樣當我們在寫程式的時候就可以注意一下程式語言內建的排序演算法是用哪種而時間複雜度又是如何，不筆記一波就會忘記囉 XD
內部排序 vs 外部排序
在 Sort 演算法裡面其實有所謂內部排序跟外部排序的兩種分類。
Internal Sort (內部排序)
指的是資料量少，可以將這些資料一次全部置於 memory 中，進行排序工作
例如：Bubble Sort、Insertion Sort、Quick Sort、Heap Sort、Radix Sort、Selection Sort
External Sort (外部排序)
指的是資料量太大，無法一次將全部資料置於 memory，必須藉助外部儲存體 (例如：Disk) 保存，在做排序工作。
採用的演算法策略是用一種：排序 - 合併的策略
也就是在排序階段，先讀入能放在內存中的數據量，將其排序輸出到一個臨時文件，依此進行，將待排序數據組織為多個有序的臨時文件，而後在合併階段將這些臨時文件組合為一個大的有序文件，也即排序結果。
例子：Merge Sort (利用 Selection Tree 結構輔助)、M-way Search Tree、B Tree。
Stable vs Unstable Sorting Method
在 Sort 演算法裡面還有所謂 Stable 跟 Unstable 的兩種分法。
定義
在輸入資料中，很可能會存在多筆具相同的資料，例如：4、1、3、k、k*、100、50。假設這邊 k 與 k 兩者的資料是一樣的，經過某個排序演算法之後，若是這個演算法保證 k 仍會在 k 之前，則稱此排序演算法為 Stable**。反之，如果無法保證，也就是 k * 有可能在 k 之前，則稱 Unstable。
為什麼兩者會有區別？
- Unstable 的演算法代表會有不必要的 swap，也就是在排序前，k 已經在 k * 前面，已經排好了，而此演算法可能還是會對兩者的位置進行交換，會造成多餘的開銷。
- 所有的 Unstable 排序演算法一定都比 stable 的演算法慢，這句話是錯的。因為著名的 Unstable 排序演算法就是 Quick Sort，而 Quick Sort 都比 Insertion Sort、Bubble Sort 這類的 Stable 排序的演算法來的快。
初等排序 vs 高等排序
這兩者的差別就在於時間複雜度效率的差別。
初等排序
在初等排序中平均時間複雜度為 $O (n^2)$，例子：
- Selection Sort
- Insertion Sort
- Bubble Sort
當然初等排序的演算法也比較簡單，通常是我們這些正常人可以想出來的演算法 XD
高等排序
在高等排序中平均時間複雜度為 $O (nlogn)$，例子：
- Quick Sort
- Merge Sort
- Heap Sort
高等排序的演算法就比較複雜！
Linear-Time Sorting Algorithm
在排序的世界裡面，還有一種類型的排序演算法，那就是線性時間的排序演算法。
而這類的演算法與上面所提到的演算法差別在於排序技巧並非採用 Comparison-based，才有可能達到 $O (n^2)$ 的時間複雜度。
Comparison-based 定義：透過「小於或等於」的操作來確定兩個元素中哪個應該放在序列前面。
非比較排序演算法例子如下：
- Radix Sort
- Bucket Sort
- Counting Sort
總結
透過知道 Sort 世界裡面常常聽到的名詞，可以了解每個排序演算法是屬於哪一種類型，又適合在怎樣的場合。
之後會一一將每種排序演算法的定義、程式碼實現、分析時間複雜度寫成文章分享給大家，其實就是我考研究所的筆記 XD 需要重新熟悉一下！
最後最後！請聽我一言！
如果你還沒有註冊 Like Coin，你可以在文章最下方看到 Like 的按鈕，點下去後即可申請帳號，透過申請帳號後可以幫我的文章按下 Like，而 Like 最多可以點五次，而你不用付出任何一塊錢，就能給我寫這篇文章的最大的回饋！