9.Algorithms: Sorting 學習筆記
學習資料來源: Master the Coding Interview: Data Structures + Algorithms
此單元會談到的數個Sort類型：Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort
【Bubble Sort】
1.從陣列第一及第二個值開始，兩兩比較，較大的值在右，直到比較完整個陣列 => 比完後最大的值會在陣列右邊第一個位置
2.第二輪一樣從頭開始兩兩比較 => 比完後第二大的值會在陣列右邊第二個位置
3.以此類推總共進行n(陣列長度)輪
示意圖
以此類推，直到最後一輪進行完畢得到 1 2 3 4 5 6 7 8
【用JS實作 Bubble Sort】
【Selection Sort】
1.從第一及第二個值開始，兩兩比較，找目前最小值，直到比較完整串數字 => 將最小值與第一個值交換
2.第二輪一樣從頭開始兩兩比較=> 比完後將第二小的值與第二個值交換
3.以此類推總共進行n(陣列長度)輪
示意圖
以此類推，直到最後一輪進行完畢得到 1 2 3 4 5 6 7 8
【用JS實作 Selection Sort】
【Insertion Sort】
輸入值數量小，或輸入值經過排序時，適合用Insertion Sort
1.陣列第二個和第一個比，較小的放右邊，第三個和前兩個比，放在符合其大小的位置，以此類推，直到比較完整個陣列
2.以此類推將各位置的項目放在適合的位置
示意圖
此輪進行完畢可得到 1 2 3 4 5 6 7 8
【用JS實作 Insertion Sort】
【Merge Sort】
Worse Case 的效率較好，記憶體容量沒有太多限制時可用
1.將陣列不斷拆半至成單一元件
2.左右兩兩一組比較，組內依大小排序後，再跟另一組比較，直到組合成新陣列
示意圖
合併完，可得到 1 2 3 4 5 6 7 8
【用JS實作 Merge Sort】
((log n)的概念類似tree的高度)
