Table of Contents
1. 使用時機
Sorting algorithms (排序演算法) 可以說是最常用到的演算法之一，主要有兩個原因：
- 任何資料在未排序前要搜尋某個元素時只能使用 linear search，從頭到尾遍歷一次，找尋目標元素，但如果是排序好的元素則可以使用 binary search, interpolation search 等搜尋演算法來查詢目標元素
- 在真實的應用中很常需要排列元素，ex: 熱門貼文、最新貼文、最近刪除的圖片等等，不同的場景適用的排序演算法也不同
2. 分類
一般來說可以依照幾種方法來分類：
2.1 Stability (穩定性)
2.1.1 Stable Sorting
兩個 value 相同的元素，在排列前後的相對位置一樣，稱為 stable sorting (穩定排序法)
2.1.2 Unstable Sorting
兩個 value 相同的元素，在排列前後的相對位置改變，稱謂 unstable sorting (不穩定排序法)
2.2 Internal and External Sorting
2.2.1 Internal Sorting (內部排序)
排序的過程中，將待排序的所有元素放置在主記憶體 (RAM)
- Bubble Sort
- Insertion Sort
- Selection Sort
- Shell Sort
- Heap Sort
- Quick Sort
- Merge Sort
2.2.2 External Sorting (外部排序)
需要排序的元素太多，無法全部置於主記憶體，整個排序過程需要在主記憶體與硬碟之中多次交換資料才能完成，external sorting 又可再分為 distribution sorting 和 external merge sort：
- Distribution Sorting：類似 quick sort，以下排序法都算 distribution sorting
- Counting Sort
- Bucket Sort
- Radix Sort
- External Merge Sort：類似 merge sort，將資料拆分為數個 subset 載入記憶體，將記憶體內的元素使用 internal sorting 排序完後，再使用 pointers merge 所有排列好的 subsets
圖片來源：External Sorting vs Internal Sorting
一般來說我們學習的排序演算法都是 internal sorting。
2.3 Complexity
可以按照演算法的複雜度分為以下兩種：
2.3.1 Simple Sorts
Simple sorts，顧名思義，很 simple，可能你我都可以自己想出來，不過相對來說時間複雜度較差，通常來說為 O(n2)
- Bubble Sort
- Insertion Sort
- Selection Sort
2.3.2 Efficient Sorts
Efficient sorts 較為複雜，但時間複雜度較 simple sorts 好，通常為 O(n log n)
- Shell Sort
- Heap Sort
- Quick Sort
- Merge Sort
3. 總結
雖然以上提到了這麼多演算法，但只會介紹比較常用的 7 種演算法，也就是 internal sorting 的那 7 種。你可能會想說學這麼多排序演算法有意義嗎？以 JavaSciprt 來說不就一個 Array.prototype.sort() (使用 quick sort implement) 就能解決所有事情了？然而，不同的排序演算法還是有它不同的應用場景。
舉例來說，今天有個社群軟體的首頁要展示前一天最熱門的 10 篇貼文，在資料庫極為龐大的情況下，就可以選擇使用 selection sort，因為它的原理是每次選擇最小的(或最大的)放在元素的最前面，如此一來就不用把所有元素排序完再取前 10，而是直接把前 10 熱門的文章排序完後，就不用再繼續排序了。
4. 參考資料
External Sorting vs Internal Sorting
External sorting – Wikipedia
如果覺得我的文章有幫助的話，歡迎幫我的粉專按讚哦~謝謝你！