Docker
Network
RxJS
Nginx
TypeScript
Data Structure And Algorithm
JavaScript
PostgreSQL
React
Git演算法筆記：排序-2 (Merge, Quick , Radix)
- 關於數字排序的演算有許多種，但因為方法不同，其時間複雜度可以從 O(n^2 )變成 O(n log (n)) ，(這裡的log是以2為底的對數)
- 一般而言，越有效率的演算法，其內部的觀念都很 tricky ，想法上並不是很直覺性的，也因此需要更多時間去理解。
- 並沒有萬用的演算法，因為不同情況下 ( 隨機排序, 近乎正排序, 近乎倒排序) ，不同的演算法所展現的效率並不同，因此針對不同情況而選擇適合演算法才是最佳解。
1. Merge Sort
- 結合
merging以及sorting兩種方法 - 將 Array 拆成無數個小 array (length =2 or 1) ，並將其重組成新的陣列
先定義 merge method ，該 function 接受 兩個各別已排序之陣列 ，將其合併成一個已排序的大陣列。
1-2 Merge Sort 的 Big O notation
由於 Merge Sort 是將一個陣列拆分成無數個長度為1的小陣列，此過程所需的次數為 log (陣列總長) ，其中的 log 為以 2 為底的對數，假如是長度為 8 的陣列，將其拆分成各個長度為 1 的小陣列所需次數為 3 次，再將所有小陣列組合成一個已排的大陣列所需的次數為8次 (總長度) ，因此對於一個長度為8的陣列而言，透過 Merge Sort 處理的時間複雜度為 24 次 (8 X log 8=24) ; 其時間複雜度相較於 Bubble、Selection 、 Insertion 的時間複雜度 (O(n^2)) ，但犧牲的是空間複雜度提升至 O(n) 。
| Algorithm | Best condition | Average | Worst | Space complexity |
|---|---|---|---|---|
| Merge Sort | O(n log (n)) | O(n log (n)) | O(n log (n)) | O(n) |
2. Quick Sort
概念是在陣列中先選定一數字做為 pivot (下方例子以 arr[0] 作為 pivot )，並將小於 pivot 的數字放在其左方，大於 pivot 的數字放置於其右方。
2-2 Quick Sort 的 Big O notation
一般情況下 (隨機排列的陣列) ，其實時間複雜度為 O (n log(n)) ，但最糟的情況會發生在 已近乎排列的陣列 上，因為對於 已近乎排列的陣列 而言， arr[0] 有極大機率是陣列內最小的數字，又因為最初的 pivot 是選在 arr[0] ，因此有可能導致 pivot function 回傳的 pivotIndex 仍為 0 ，也因此所需要的迭代次數就會增加，時間複雜度變為 O (n^2) 。
| Algorithm | Best condition | Average | Worst | Space complexity |
|---|---|---|---|---|
| Quick Sort | O(n log (n)) | O(n log(n)) | O(n^2) | O(log n) |
3. Radix Sort
Radix Sort (基數排序法) 比較特別，屬於 non-comparative 的排序演算法，針對每一位數來達到排序的目的，下方程式碼中的 getDigit function 接收 input(num &index) ，並回傳該 num 在某位數 (index) 的值。
3-3 Radix Sort 的 Big O notation
O (nk) 中的n表示陣列的長度， k 則表示陣列中最大數字的位數 (digits) ，由於在任何情況下的時間複雜度皆相同 (O (nk)) 。
| Algorithm | Best condition | Average | Worst | Space complexity |
|---|---|---|---|---|
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) |