-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path1-10-4.html
312 lines (289 loc) · 11 KB
/
1-10-4.html
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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
<!DOCTYPE html>
<html lang="zh-TW">
<head>
<meta charset="UTF-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<link rel="icon" href="./public/favicon.ico" />
<meta http-equiv="cache-control" content="no-cache" />
<title></title>
<link rel="stylesheet" href=" https://necolas.github.io/normalize.css/8.0.1/normalize.css" />
<link rel="stylesheet" href="./hightlight/default.min.css" />
<link rel="stylesheet" href="./css/main.css" />
<link rel="stylesheet" href="./css/copybutton.css" />
<link rel="stylesheet" href="./css/hightlight.css" />
<script src="./hightlight/hightlight.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/clipboard.js/2.0.11/clipboard.min.js"></script>
<!-- Google tag (gtag.js) -->
<script async src="https://www.googletagmanager.com/gtag/js?id=G-BEVZJDBC7Z"></script>
<script src="./js/gtag.js"></script>
</head>
<body>
<header>
<nav>
<h1>
<span id="toggle-menu"></span>
<a href="index.html"></a>
</h1>
</nav>
</header>
<main>
<aside>
<nav></nav>
</aside>
<article>
<h2 id="1-10-4">1-10-4 Sorting Algorithms 排序演算法 進階</h2>
<h3>Merge Sort</h3>
<p>原則1 當在合併一個已經排序好的陣列時，演算法的時間複雜度為 O(n)</p>
<p>原則2 分而治之(divide and conquer)</p>
<p>分割大問題為小塊個別處理。</p>
<p>
實作思路：假設有一個無序集合，將集合拆成一半，切出的子集合全部個別再拆成一半，以此類推直到切到每一個子集合的
length 剩 1
(無法再分割)。這個時候每一個子集合單元都因為只有一個元素，所以可以視為一個已排序的集合。再將每一個已排序集合兩兩分成一組合併，分完組每組再做排序，排完序再兩兩分成一組合併，以此類推將集合排序重新組裝成新的已排序集合。
</p>
<p>
排序的實作方法可以使用 Pointer
的概念，將需要合併的陣列列舉出來。因為都是排序好的集合所以可以從 2
個集合的最前頭開始比較，把最小值取出來放到新的合併集合中，直到 2
個待合併的集合的元素全部取完即完成合併。
</p>
<pre><code class="language-js">
function merge(a1, a2) {
let result = [];
let i = 0;
let j = 0;
while (i < a1.length && j < a2.length) {
if (a1[i] > a2[j]) {
result.push(a2[j]);
j++;
} else {
result.push(a1[i]);
i++;
}
}
// a1 or a2 might have some elements left
// use loop to put them all into result
while (i < a1.length) {
result.push(a1[i]);
i++;
}
while (j < a2.length) {
result.push(a2[j]);
j++;
}
return result;
}
function mergeSort(arr) {
if (arr.length === 1) {
return arr;
} else {
let middle = Math.floor(arr.length / 2);
let left = arr.slice(0, middle);
let right = arr.slice(middle, arr.length);
return merge(mergeSort(right), mergeSort(left));
}
}
console.log(mergeSort([15, 3, 17, 18, 35, 11, 0, 36, -336, 1054]));
</code></pre>
<p>
空間複雜度比較高，因為從上面範例可以看到這過算法會不斷開起新的記憶體空間，暫時存放已分割的排序子集合，故使用到的記憶體比較多。
</p>
<p>
合併時需要將每一個元素都做比較和抓取，故假設有一個 length 為 n 的集合，要做合併的 step
次數計算為 (第1次 n/2)..(第2次 n/4)..(第3次 n/8)最後得到一個算式 n/2ᵐ = 1。轉化公式為求 m
值 變成 n = 2ᵐ 在轉化一次 m = log₂n ， 得到 m ，意思是合併 m 步驟會合併完畢。
每一個步驟都要再合併 n 次。故最終得到 merge sort 的時間複雜度公式為 n log₂n。換成 BigO
值為 O(n log n)。
</p>
<p>上述函式的 BigO 時間複雜度:</p>
<ul>
<li>最糟情況： O(n log n)</li>
<li>最好情況： O(n log n)</li>
<li>平均情況： O(n log n)</li>
</ul>
<h3>資料結構-Tree</h3>
<p>
Tree 是一種常見的抽象資料結構。畫成圖片的話我們會先看到一個原始起點。每一個點叫做 Node ，
初始點為 Root ， Node 跟 Node 之間的連接指向為 edge。每一個樹狀結構一定有、只會有一個
Root。 Node 之間有分母子層級。兩個相接的 Node 一定會分母子，較為接近 Root 的為母節點
Parent Node ，相對較遠的為子節點 Children Node。如果將某串 Node 獨立劃分來就叫做整個 Tree
的 Subtree。最後還有一個定義： Node 組不能形成一個閉環。
</p>
<p>
這邊會先談到其中一種 Tree ，因為接下來要介紹的
排序法會使用這種樹狀結構來搭配。之後的章節會再次提到更加完整的內容，以及列舉介紹其他樹狀結構。
</p>
<h3>Tree - Max Heap</h3>
<p>定義1.：每一個作為母節點的 Node 必須有兩個子節點。</p>
<p>
定義2.：每一個 Subtree 的 Root 節點所裝載的數字必為該 Subtree 所有節點比較後的最大值。
</p>
<h3>Heap Sort Algorithm</h3>
<p>buildMaxHeap: 幾個 node 就會執行幾次。由 heapSize / 2 開始。</p>
<p>
maxHeapify:
先以3節點為一組的樹做相互交換位置，最後將最大值往樹的母層交換，較小的值往子層交換的一個方法。
</p>
<pre><code class="language-js">
let heapSize;
let arr = [15, 3, 17, 18, 20, 2, 1, 666];
heapSort();
console.log(arr);
function buildMaxHeap() {
heapSize = arr.length - 1;
for (let i = Math.floor(heapSize / 2); i >= 0; i--) {
maxHeapify(i);
}
}
function maxHeapify(i) {
let largest;
let l = i * 2 + 1;
let r = i * 2 + 2;
if (l <= heapSize && arr[l] > arr[i]) {
largest = l;
} else {
largest = i;
}
if (r <= heapSize && arr[r] > arr[largest]) {
largest = r;
}
if (largest != i) {
// swap A[i] with A[largest]
let temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
maxHeapify(largest);
}
}
function heapSort() {
buildMaxHeap();
for (let i = arr.length - 1; i >= 0; i--) {
// exchange A[0] with A[i]
let temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapSize -= 1;
maxHeapify(0);
}
return arr;
}
</code></pre>
<p>上述函式的 BigO 時間複雜度:</p>
<ul>
<li>最糟情況： O(n log n)</li>
<li>最好情況： O(n log n)</li>
<li>平均情況： O(n log n)</li>
</ul>
<h3>Quick Sort Algorithm and partition</h3>
<p>
快速排序的特點就是分治。如何表現分治策略呢？我們首先在陣列中選取一個基準點，將其稱為pivot，根據這個基準點，把比基準點小的陣列值放在基準點左邊，把比基準點大的陣列值放在基準點右邊。這樣一來，基準點的左邊分區的值都小於基準點，右邊分區的值都大於基準點，然後針對左邊分區和右邊分區進行同樣的操作，直到最後排序完成。
最簡單的實現如下。
</p>
<pre><code class="language-js">
let arr = [15, 3, 17, -17, 3.1415, 18, 20, 2, 1, 666];
function partition(p, r) {
let x = arr[r]; // pivot
let i = p - 1;
for (let j = p; j <= r - 1; j++) {
if (arr[j] <= x) {
i += 1;
// swap arr[i] and arr[j]
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[r]
let temp = arr[i + 1];
arr[i + 1] = arr[r];
arr[r] = temp;
return i + 1;
}
function quickSort(p, r) {
if (p < r) {
let q = partition(p, r);
quickSort(p, q - 1);
quickSort(q + 1, r);
}
}
quickSort(0, arr.length - 1);
console.log(arr);
// [-17, 1, 2, 3, 3.1415, 15, 17, 18, 20, 666]
</code></pre>
<p>
試想一下，如果我們對一個已經有序的陣列進行排序，剛好每次選擇 pivot
時總是選擇第一個或最後一個元素，那麼每次都會有一個數區是空的，遞迴的層數將達到n，最後會導致演算法的時間複雜度退化為O(n²)。因此
pivot 的選擇非常重要。
</p>
<p>
在早期的 V8引擎中使用快速排序時，會採用三數取中（median-of-three）的 pivot
最佳化方案：除了頭尾兩個元素，再額外選擇一個元素參與基準點的競爭。實際原始程式如下。
</p>
<pre><code class="language-js">
var GetThirdIndex = function (a, from, to) {
var t_array = new InternalArray();
// Use both 'from' and 'to' to determine the pivot candidates.
var increment = 200 + ((to - from) & 15) ;
var j= 0;
from += 1;
to -= 1;
for (var i = from; i < to; i += increment) {
t_array[j] = [i, a[i]];
j++;
}
t_array.sort (function (a, b) {
return compareFn(a[1], b[1]);
});
var third_index = t_array[t_array.length > 1][0];
return third_Index;
}
var Quicksort = function Quicksort (a, from, to) {
while (true) {
if (to - from > 1000) {
third index = GetThirdIndex (a, from, to) ;
} else {
third_index = from + ((to-from)>>1);
}
}
.....
};
</code></pre>
<p>由此可以看出，所謂的第三個競爭元素的產生方式如下。</p>
<ul>
<li>當陣列長度小於等於1000時，選擇折半位置的元素作為目標元素。</li>
<li>
當陣列長度超過1000時，每隔200~215（非固定，跟著陣列長度而變化）個值就選擇一個元素來確定一批候選元素。接著，在這批候選元素中進行一次排序，將獲得的中位數作為目標元素。
</li>
</ul>
<p>在三數取中的方案中，最後會將3個元素的中位數作為 pivot。</p>
<p>上述函式的 BigO 時間複雜度:</p>
<ul>
<li>最糟情況： O(n²)</li>
<li>最好情況： O(n log n)</li>
<li>平均情況： O(n log n)</li>
</ul>
<p></p>
<pre><code class="language-js">
</code></pre>
<pre><code class="language-js">
</code></pre>
<pre><code class="language-js">
</code></pre>
<pre><code class="language-js">
</code></pre>
<pre><code class="language-js">
</code></pre>
<pre><code class="language-js">
</code></pre>
<pre><code class="language-js">
</code></pre>
<pre><code class="language-js">
</code></pre>
<pre><code class="language-js">
</code></pre>
</article>
</main>
</body>
<script type="module" src="./js/main.js"></script>
</html>