JavaScript Sorting
早學晚學都要的排序 6 位大大們 XD
最近在上 資料結構與演算法 (JavaScript) 的課程 ( 蠻推的 )
這門課是依照 Introduction to Algorithms ( 第三版 CLRS 版 ) 的課綱編排的課程
就是 零基礎的小明要如何成為前端工程師？
裡面 [ 於是長大了以後 ] 那段，小明手中的Introduction to Algorithms
自己整理過會有比較有映像，希望遇到白板可以寫的出來 XD
也推薦大家理解或是自己整理看看
3 種簡單排序 & 3 種進階排序
以下所有的 code :
1 | let arr = [4, 1, 5, 2, 7] |
以下註解版 :
泡沫排序 Bobble
- 簡單排序法之一
- 時間複雜度 : O(n²)
- 邏輯 : 兩兩左右交換
- 實作 : 雙重迴圈
- code :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16function sort(arr) {
for (let i = 0; i < arr.length - 2; i++) {
for (let j = i; j < arr.length - 1; j++) {
// 如果 j 大於 j + 1 項 => 兩者交換
if (arr[j] > arr[j+1]) {
// 交換 j & j + 1
arr[j] = arr[j] + arr[j+1]
arr[j+1] = arr[j] - arr[j+1]
arr[j] = arr[j] - arr[j+1]
}
}
console.log(arr) // debug
}
return arr
}
console.log(sort(arr))
插入排序法 Insertion
- 簡單排序之一
- 時間複雜度 : O(n²)
- 邏輯 : 從左到右，將右邊的數插入正確的位置
- 實作 : for 迴圈 + while 迴圈
- code :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17function sort(arr) {
for (let j = 1; j < arr.length - 1; j++) {
// key 為當前的值
let key = arr[j]
// 從 key 的左邊開始找
let i = j - 1
// 當 arr[i] 的值大於 key ， 將 i + 1 的位置空出來
while( i >= 0 && arr[i] > key){
arr[i + 1] = arr[i]
i--
}
// 將 key 放入 i + 1 位置
arr[i+1] = key
// console.log(arr) // debug
}
return arr
}
選擇排序法 Selection
- 簡單排序法之一
- 時間複雜度 : O(n²)
- 邏輯 : 依序選擇最小的值，排到最前面
- 實作 : 雙重迴圈
- code :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17function sort(arr) {
for (let i = 0; i < arr.length - 2; i++) {
let minIndex = i
for (let j = i; j < arr.length - 1; j++) {
// 找出最小值
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 將最小值交換到最前面
arr[i] = arr[i] + arr[minIndex]
arr[minIndex] = arr[i] - arr[minIndex]
arr[i] = arr[i] - arr[minIndex]
// console.log(arr) //debug
}
return arr
}
合併排序法 Merge
- 進階排序之一
- 時間複雜度 : O(n * log n)
- 邏輯 : divide and conquer ，將 array 拆成較小的 array 再排序
- 實作 : 拆成兩個 function
- marge : 將兩個排序好的 array 合併成一個 array
- sort ( 遞迴 ) : 將 array 拆成左右兩個 array
- code :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34function merge(arr1, arr2) {
let result = []
let i = j = 0
// 將 arr1 或 arr2 較小的數放入 result
while(i < arr1.length && j < arr2.length) {
if (arr1[i] < arr2[j]) {
result.push(arr1[i])
i++
} else {
result.push(arr2[j])
j++
}
}
// 如果其中一個放完了，將剩下的放入 reslut
while(i < arr1.length) {
result.push(arr1[i])
i++
}
while(j < arr2.length) {
result.push(arr2[j])
j++
}
return result
}
function sort(arr) {
// 如果長度等於 1 就已經排序好了
if (arr.length === 1) return arr
// 將 mid 設為 arr 的中點
let mid = Math.floor(arr.length / 2)
let left = arr.slice(0, mid)
let right = arr.slice(mid, arr.length)
// 將左右兩個 array 合併 ( sort 會回傳排序好的 array )
return merge(sort(left),sort(right))
}
堆積排序 Heap Sort
- 進階排序之一
- 時間複雜度 : O(n * log n)
- 邏輯 : 使用 Max Heap 最大堆積樹的特性來進行排序
- 實作 : 拆成三個 function
- BuildMaxHeap : 建立 Max Heap 樹，將原 array 轉成 Max Heap
- MaxHeapify ( 遞迴 ) : 維持 Max Heap
- sort : 一開始先建立 Max Heap，將 arr[0] ( 最大值 ) 換到最後面，並且將它排除 Max Heap 再去呼叫 MaxHeapify(0) 繼續維持 Max Heap
- code :
1 | let heapSize |
快速排序 Quick Sort
- 進階排序之一
- 時間複雜度 : O( n * log n )
- 邏輯 : 選擇一個樞 ( pivot )，將比他大的分到右邊、比他小的分到左邊，則這一個樞已經排序好了
- 實作 : 拆成兩個 function
- partition : 依照樞的值分左右各一組，並且回傳已排序好樞的 index
- sort ( 遞迴 ) : 將 array 分成三個部分，q ( 已排序好的 index )、arr[p, q - 1]、arr[q + 1, r]，遞迴呼叫自己排序左右兩個 array，產生更多排序好的 index
- code :
1 | function partition(p,r) { |