-
Notifications
You must be signed in to change notification settings - Fork 0
/
1-10-3.html
145 lines (138 loc) · 5.12 KB
/
1-10-3.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
<!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-3">Sorting Algorithms 排序演算法 初階</h2>
<h3>Bubble Sort</h3>
<p>遍歷一個集合，依序比較相鄰兩個元素，根據排序條件決定是否互換位置。</p>
<p>
以下為 Bubble Sort 範例，由於本範例實作上 BigO
的時間複雜度太高，僅作為教學用，因此本範例並不建議用在實際專案上。
</p>
<pre><code class="language-js">
function bubbleSort(arr) {
let step = 0;
for (let i = 0; i <= arr.length - 2; i++) {
let swapping = false;
for (let j = arr.length - 1; j >= i + 1; j--) {
if (arr[j] < arr[j - 1]) {
// swap arr[j] and arr[j - 1]
let temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
step++;
}
}
if (swapping == false) {
break;
}
}
console.log("It takes " + step + " steps to complete.");
console.log(arr);
}
let test = [];
for (let i = 0; i < 100; i++) {
test.push(Math.floor(Math.random() * 100));
}
bubbleSort(test);
</code></pre>
<p>上述函式的 BigO 時間複雜度:</p>
<ul>
<li>最糟情況： O(n²) 執行第二層迴圈 1 次。</li>
<li>最好情況： O(n) 本來就排序完成，第二個迴圈不用跑，只做檢查走一遍。</li>
<li>平均情況： O(n²) 執行第二層迴圈 n 次。</li>
</ul>
<h3>Insertion Sort</h3>
<p>
遍歷一個集合，迴圈走到的元素和該元素前一個元素做條件比較，若該元素符合換位條件，就將該元素往已經遍歷過的子集合插入。不符合的就接著看下一個元素。簡單講從「未排序好的數字」中找到最小值，把最小值丟到「未排序好的數字」的最左邊，把它標示成已排序好。
</p>
<pre><code class="language-js">
function insertionSort(arr) {
for (let j = 1; j <= arr.length - 1; j++) {
let key = arr[j];
i = j - 1;
while (i >= 0 && arr[i] > key) {
arr[i + 1] = arr[i];
i -= 1;
}
arr[i + 1] = key;
}
console.log(arr);
return arr;
}
let unsorted = [14, -4, 17, 6, 22, 1, -5];
insertionSort(unsorted);
</code></pre>
<p>上述函式的 BigO 時間複雜度:</p>
<ul>
<li>最糟情況： O(n²) 執行第二層迴圈 1 次。</li>
<li>最好情況： O(n) 本來就排序完成，第二個迴圈不用跑，只做檢查走一遍。</li>
<li>平均情況： O(n²) 執行第二層迴圈 n 次。</li>
</ul>
<h3>Selection Sort</h3>
<p>
首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
選擇排序的主要優點與資料移動有關。如果某個元素位於正確的最終位置上，則它不會被移動。
</p>
<pre><code class="language-js">
function selectionSort(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;
}
}
// swap arr[minIndex] and arr[i]
let temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
console.log(arr);
}
console.log(arr);
return arr;
}
let unsorted = [14, -4, 17, 6, 22, 1, -5];
selectionSort(unsorted);
</code></pre>
<p>上述函式的 BigO 時間複雜度:</p>
<ul>
<li>最糟情況： O(n²) 執行第二層迴圈至少 1 次。</li>
<li>最好情況： O(n²) 執行第二層迴圈 1 次。</li>
<li>平均情況： O(n²) 執行第二層迴圈 n 次。</li>
</ul>
</article>
</main>
</body>
<script type="module" src="./js/main.js"></script>
</html>