早學晚學都要的排序 6 位大大們 XD
最近在上 資料結構與演算法 (JavaScript) 的課程 ( 蠻推的 )
這門課是依照 Introduction to Algorithms ( 第三版 CLRS 版 ) 的課綱編排的課程
就是 零基礎的小明要如何成為前端工程師？
裡面 [ 於是長大了以後 ] 那段，小明手中的
Introduction to Algorithms
自己整理過會有比較有映像，希望遇到白板可以寫的出來 XD
也推薦大家理解或是自己整理看看
3 種簡單排序 & 3 種進階排序
以下所有的 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
| let arr = [4, 1, 5, 2, 7]
console.log(arr)
console.log('^^^ original ^^^')
|
以下註解版 :
泡沫排序 Bobble
- 簡單排序法之一
- 時間複雜度 : O(n²)
- 邏輯 : 兩兩左右交換
- 實作 : 雙重迴圈
- code :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| function sort(arr) {
for (let i = 0; i < arr.length - 2; i++) {
for (let j = i; j < arr.length - 1; j++) {
if (arr[j] > arr[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)
}
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
17
| function sort(arr) {
for (let j = 1; j < arr.length - 1; j++) {
let key = arr[j]
let i = j - 1
while( i >= 0 && arr[i] > key){
arr[i + 1] = arr[i]
i--
}
arr[i+1] = key
}
return arr
}
|
選擇排序法 Selection
- 簡單排序法之一
- 時間複雜度 : O(n²)
- 邏輯 : 依序選擇最小的值，排到最前面
- 實作 : 雙重迴圈
- code :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| function 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]
}
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
34
| function merge(arr1, arr2) {
let result = []
let i = j = 0
while(i < arr1.length && j < arr2.length) {
if (arr1[i] < arr2[j]) {
result.push(arr1[i])
i++
} else {
result.push(arr2[j])
j++
}
}
while(i < arr1.length) {
result.push(arr1[i])
i++
}
while(j < arr2.length) {
result.push(arr2[j])
j++
}
return result
}
function sort(arr) {
if (arr.length === 1) return arr
let mid = Math.floor(arr.length / 2)
let left = arr.slice(0, mid)
let right = arr.slice(mid, arr.length)
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
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
34
35
36
37
38
39
40
41
42
43
44
45
| let heapSize
function sort(arr) {
BuildMaxHeap()
for (let i = arr.length - 1; i > 0; i--) {
arr[0] = arr[0] + arr[i]
arr[i] = arr[0] - arr[i]
arr[0] = arr[0] - arr[i]
heapSize--
MaxHeapify(0)
}
return arr
}
function BuildMaxHeap() {
heapSize = arr.length - 1
for (let i = Math.floor(heapSize/2); i >= 0; i--) {
MaxHeapify(i)
}
}
function MaxHeapify(i) {
let l = i * 2 + 1
let r = i * 2 + 2
let largest = (l <= heapSize && arr[l] > arr[i]) ? l : i
largest = (r <= heapSize && arr[r] > arr[largest]) ? r : largest
if (largest !== i) {
arr[largest] = arr[largest] + arr[i]
arr[i] = arr[largest] - arr[i]
arr[largest] = arr[largest] - arr[i]
MaxHeapify(largest)
}
}
|
快速排序 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
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
34
35
36
37
38
39
40
| function partition(p,r) {
let x = arr[r]
let i = p - 1
for (let j = p; j < r; j++) {
if (arr[j] <= x) {
i++
if (i === j) continue
arr[i] = arr[i] + arr[j]
arr[j] = arr[i] - arr[j]
arr[i] = arr[i] - arr[j]
}
}
if (i + 1 === r) return i + 1
arr[i + 1] = arr[i + 1] + arr[r]
arr[r] = arr[i + 1] - arr[r]
arr[i + 1] = arr[i + 1] - arr[r]
return i + 1
}
function sort(p, r) {
if (p < r) {
let q = partition(p,r)
sort(p, q - 1)
sort(q + 1, r)
}
}
sort(0, arr.length - 1)
|
Ref.
