Docker
Network
RxJS
Nginx
TypeScript
Data Structure And Algorithm
JavaScript
PostgreSQL
React
Git演算法筆記：排序-1 (Bubble, Selection, Insertion)
在這裡紀錄學習 Data Structure & Algorithm 的學習筆記，在這邊會記錄三種排序的演算法，分別為
- Bubble Sort
- Selection Sort
- Insertion Sort
1. Bubble sort
將陣列內的數字，兩兩作比對，數字較小移到前面，反之則不動，持續進行，時間複雜度在一般情況下為 O(n^2) ，但是若針對 幾乎已排列完成 的數列而言，時間複雜度則是 O(n) 。
1-2 優化後的Bubble sort
在 Bubble Sort 內定義一個用來監控的變數 noSwaps ，假如最近的一次 loop 沒有進行陣列上的交換，則立即跳出 loop ，避免後續無意義的運算。
2. Selection Sort
該演算法的概念是透過每一步都將陣列內的最小值放到陣列的最前頭，最好以及最壞的情況下，它的時間複雜度皆為 O(n^2) 。
3. Insertion Sort
概念是擇一數字放置於比它大的左邊，比它小的右邊，時間複雜度是 O(n^2) ，但是若針對 幾乎已排列完成 的數列而言，時間複雜度則是 O(n) 。
也可以寫成
比較上述三種演算法的 Big O Time Complexity
| Algorithm | Best condition | Average | Worst | Space complexity |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) |
| Insertion Sort | O(n) | O(n^2) | O(n^2) | O(1) |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) |
基本上 Bubble , Selection , Insertion 三種方法的時間複雜度在一般的情況下(隨機排列的數字)，都是一樣的 (O(n^2)) ，若要將其降至 O(n^2) 以下，就需要靠較複雜的演算法。在下一篇會介紹到效率更好，但相對較複雜的排序演算法。