When to Use Static Generation v.s. Server-side Rendering

Two Forms of Pre-rendering

費波那契數列是常見的面試考題，一般來說有分迴圈的解法（iterative solution）和遞迴的解法（recursive solution） 。<figure><img alt="" src="https://cdn-images-1.medium.com/max/352/1*J19lh6cMPpxbjUtZj-0r4A.png" /><figcaption>Recursive Solution</figcaption></figure>使用遞迴的解法時，runtime 會呈 2 的 n 次方的指數成長，當輸入的 n 值越大時，執行時間就會戲劇性地變化成越來越長。如果今天的情況是非使用遞迴不可，那要怎麼來提升執行速度呢？這時候可以使用 cache 的方式來記憶已經處理過的 fib。寫一個命名為 memoize 的函式，這個函式會回傳一個匿名函式，在這匿名函式之中判斷 cache 內是否已經存有處理過的 fib，有的話直接回傳 cache 內的值：<figure><img alt="" src="https://cdn-images-1.medium.com/max/445/1*hDw0ehntN_v-qwCFp0gBmw.png" /></figure>接著將本來的 fib 函式傳入 memoize 函式，並執行 fib 就會得到答案了。這裡的時間複雜度會降為 O(n)，解決了遞迴效率低落的問題。<figure><img alt="" src="https://cdn-images-1.medium.com/max/207/1*LSqkz5AO3Qh_7PFsu0ZFaw.png" /></figure>完整的程式碼如下：<figure><img alt="" src="https://cdn-images-1.medium.com/max/446/1*MRXUXZiSJF9enZiYWG6-sA.png" /></figure>有查到使用 cache 的另一種寫法，也記錄一下：<figure><img alt="" src="https://cdn-images-1.medium.com/max/739/1*VQXes8HrQCXPY50l5NJl5Q.png" /></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e642263fbb99" width="1" height="1" alt="">

Fibonacci 數列：使用 cache 的遞迴解法

覺得有些 method 太常忘記要一直估狗，決定整理在一起筆記一下<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*KAdHdnWWKJtWpq2dYtk_MA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*iuZ-3WcB_iyYqN0gLaiyAA.png" /></figure>Destructuring assignment syntax<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*R4zYh4VN98sAVM7k2dnnIA.png" /><figcaption>Object 不是複製參考而已</figcaption></figure><pre>let a, b, rest; [a, b] = [10, 20]; console.log(a); // expected output: 10 console.log(b); // expected output: 20 [a, b, ...rest] = [10, 20, 30, 40, 50]; console.log(rest); // expected output: Array [30,40,50]</pre><blockquote>參雜一點 functional progrmming 的觀念</blockquote><blockquote>透過 [...data] 的方式傳入一個新的陣列，可以避免原來的 data 陣列被改變，除此之外，我們也可以用一些不會改變身列本身內容的操作來操作陣列內容，例如新增一個新元素，比起使用 data.push(100)，使用 const data2 = [...data, 100] 這種寫法可以讓我們不要改到 data 本身，這種操作我們成為「 immutable (不可變的)」。</blockquote><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5d50a4dcc73e" width="1" height="1" alt="">

js array 常見操作

快速排序法的核心思維：Partition1. 在 Array 中找到一個元素 Pivot 當中間點2. 將 Array 元素重新排列，讓左半邊元素小於 Pivot，右半邊元素大於 Pivot3. 以上這兩件事可以在 O(n) 時間內做到Pseudocode of Partition<pre>Partition(p, r){ x = A[r] //將陣列最後一個項目當作 pivot i = p - 1 for(j from p to r-1(inclusice){ if(A[j] <= x){ i = i + 1 exchange A[i] with A[j] } } exchange A[i + 1] with A[r] return i + 1</pre><pre>**這裡的 i 用來代表小於 pivot 的數目</pre>假設有一個陣列 [2, 5, 7, 3, 1, 4]依照 Pseudo Code:p = 0 ，r = 5，所以 x = 4 ，一開始的 i = -1<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*7YBt5s1nf5wrH9V6I1yUlA.png" /></figure>迴圈開始，從索引位置 0 到位置 4 內的數來與 4 做比較 (pivot) 。2 < 4，所以 i + 1，此時 i 跟 j 在同一個位置，所以陣列順序不變。<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*GzPycVnN2_3rTO1LTmz1vQ.png" /></figure>迴圈繼續，接著 j 往前移一格，5 > 4，所以 j 繼續前進<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*COstyJewgXuIOojLGMrP2A.png" /></figure>發現 7 也大於 4，j 繼續前進到 3 的位置<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ZRAlCgZvg__ZTjrxzn3kZA.png" /></figure>因為 3 < 4 ，所以將 i 前進一格，並與 5 互換位置 (A[i] exchange with A[j])<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*RbdrYEEyDSs7JsoSmxzOcg.png" /></figure>以此類推，走到迴圈的最末<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*25vWnii9iDmeEaar2GT-zw.png" /></figure>exchange A[i+1] with A[r]<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*IskV36UdE_honjs-9B83Mg.png" /></figure>函數最後回傳 i + 1。這樣就找到了 pivot 在陣列中的正確位置了，其左邊的數值都比它小，右邊的數值都比它大。程式碼如下:<figure><img alt="" src="https://cdn-images-1.medium.com/max/631/1*HQiU-2TExgDpLalN5NueHA.png" /><figcaption>Quick Sort Version 1</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/636/1*-cFbewh8NlLE1Xjty3sEmg.png" /><figcaption>Quick Sort Version 2</figcaption></figure>通常我們寫 Quick Sort 時，會希望可以做到 in-place 排序，也就是不再浪費額外的暫存用記憶體，直接對原始的 Array 做改動，因為這是 Quick Sort 演算法的一大優點。因此僅將要處理的範圍資訊傳進遞迴的過程之中，且由於修改時是直接改動原始的 Array，因此也不需要回傳值了。整個 QuickSort 的時間複雜度是 O(n log n)。因為他們的遞迴深度都是 O(log n)（每次都是切一半，所以只需要 logN 步就會切到最小單位），而 Merge Sort 的後處理與 Quick Sort 的預處理都是 O(n)，所以最終乘起來就是 O(n log n) 啦。<img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8dc5ea7b2c04" width="1" height="1" alt="">

排序演算法(4)-Quick Sort

有一個解題的方法叫做 Divide and Conquer。中文直譯的話是：分割與征服。就是說把大問題拆解成小問題，再一一去征服它假設一開始有一個長度為 8 的陣列，我們將它切成一半。<figure><img alt="" src="https://cdn-images-1.medium.com/max/916/1*JxtLTGHPwzoRdoO0M9JcLg.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/883/1*rb3gn0fa5uc3aH61VfaZag.png" /></figure>接著再切一半：<figure><img alt="" src="https://cdn-images-1.medium.com/max/915/1*2NUbGtV_lYN4b8pETudp8Q.png" /></figure>接著再切一半，直到全部都被拆解成只有一個元素的 Sorted Array<figure><img alt="" src="https://cdn-images-1.medium.com/max/976/1*2My5qe5xoEaAbQgv_-leGg.png" /></figure>我們就可以設 pointer: i 跟 j ， 來一一遍歷被拆解的最小陣列，i 與 j 比大小，就能重新排序，組合成更大的陣列。<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9E3zJx6JxwqJUdo0A81U8w.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*SYhlxn90uTfzOUljjpvG5A.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ENlDIacGXkL-PBDL8ZOBGA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1020/1*Cqx1OctBn9htITaz9sdnDA.png" /></figure>這樣我們就得到兩個一組已排序好的小陣列，接著再以同樣的邏輯來組合成更大的陣列：<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*35hVfKxJexPe_j6HWl2jDw.png" /></figure>1 跟 38 比，1 比較小，所以 1 被排序到最前面。pointer j 往後移動<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_7HCEcDiL7fLm-oaRiLDFg.png" /></figure>15 跟 38 比，15 也比較小，所以 15 被排序到 1 之後。<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*sFAMPgykEwIBOWWiU-ZUlQ.png" /></figure>此時，j 也超過了其陣列長度。所以將pointer i 所屬的陣列 元素 38 跟 42 依序排列到較大的陣列。<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Hjd8FqOPF3C6wl3DikOyCg.png" /></figure>右方陣列也以此類推<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-yFUCjRWoQ9w6D3T0HaenQ.png" /></figure>再次在左右方陣列設定 pointer i 跟 j 後，依照同樣邏輯進行排序。<figure><img alt="" src="https://cdn-images-1.medium.com/max/996/1*JFOllBsqL94IWxgBEAcSMg.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/993/1*SdZVB3EACJp8KlmqW4h45w.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1021/1*xybJd1iTdQxVeCUye-NEXA.png" /></figure>….….最後就會得到整個排序過的陣列了。<figure><img alt="" src="https://cdn-images-1.medium.com/max/995/1*2NxkzJdqcW8sg683Bdr4cA.png" /></figure>時間複雜度呢？<figure><img alt="" src="https://cdn-images-1.medium.com/max/976/1*2My5qe5xoEaAbQgv_-leGg.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/671/1*iaTaWGn5jMLhsSKILQywhA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/677/1*1mXYp7FGRLl7sxdcgBEk9A.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/648/1*h_bJVuZUGBBsOWXpmev_xw.png" /></figure>從最小的元素到最後組合成原始長度的排序陣列，經歷了 3 次 Merge。這個 3 次是怎麼來的呢？<blockquote>因為 2 的 3次方 = 8</blockquote>若陣列長度為 N，那 Merge 的次數就是 logN。而每次 Merge 都會經歷 N 次比大小排序，以此例來說每一輪都會經歷8次。<blockquote>每回合的合併需要花：O(n)</blockquote><blockquote>總共需要回合數：O(log n)</blockquote>→ → 所以不管什麼情形之下的時間複雜度都是 O(n log n)。程式碼實作如下，我們會需要寫兩個 function，一個是 merge()，一個是 mergeSort()，並且會用到 遞迴 (Recursive) 的概念。<figure><img alt="" src="https://cdn-images-1.medium.com/max/680/1*Qcit_cMHIfNBj3P_mmInig.png" /></figure>加入 console.log 來看看程式的運作，是否如前述圖片演示的過程。<figure><img alt="" src="https://cdn-images-1.medium.com/max/650/1*hHaQZ52MiA0kdU26KzGpyg.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/670/1*uL3R13cS9OTdsYfWObA_Jg.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/479/1*F3enSilBduGf4thV1IqcEg.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/466/1*e7054G-1OfeES6Nx2D9Jeg.png" /></figure>Merge Sort 的缺點之一就是在合併子序列時，需要額外的空間依序插入排序資料；遞迴版本的 Mergesort 還需額外加上遞迴花費的 call stack 空間，因此額外空間複雜度為 O(n) + O(log n) = O(n)。<img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5b0de98c7b00" width="1" height="1" alt="">

排序演算法-(3) Merge Sort

藉由這題來學習 Sliding Window 技巧。題目如下:<pre>Given a string s, find the length of the longest substring without repeating characters.</pre><pre>— — — — — — — — — — — — — — — — — — — — — — — — — — — —</pre><pre>Example 1:</pre><pre>Input: s = “abcabcbb” , Output: 3</pre><pre>Explanation: The answer is “abc”, with the length of 3.</pre><pre>— — — — — — — — — — — — — — — — — — — — — — — — — — — —</pre><pre>Example 2:</pre><pre>Input: s = “bbbbb” , Output: 1</pre><pre>Explanation: The answer is “b”, with the length of 1.</pre><pre>— — — — — — — — — — — — — — — — — — — — — — — — — — — —</pre><pre>Example 3:</pre><pre>Input: s = “pwwkew” , Output: 3</pre><pre>Explanation: The answer is “wke”, with the length of 3.</pre><pre>Notice that the answer must be a substring, “pwke” is a subsequence and not a substring.</pre><pre>— — — — — — — — — — — — — — — — — — — — — — — — — — — —</pre><pre>Constraints:</pre><pre>0 <= s.length <= 5 * 104</pre><pre>s consists of English letters, digits, symbols and spaces.</pre>我們先假設 兩個 pointer: Start 和 End，初始位置都是 0。然後有一個物件類型的記分板 counter，一開始裡面什麼元素都沒有。紫色方框代表 Sliding Window，第一個條件先以 end 指到的字串位置來找尋 counter 內是否有該字母，假如沒有，就在計分板上 + 1。同時，我們會不斷更新現在 Sliding Window 的長度 (其實也相等於 counter 的長度 === 最長的 Substring，用變數 max 來表示 )，可以想像成如下圖：<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*6Sx9Xvuq_uN7XQjGdEuYsg.png" /></figure>然後 end 會往右移動一位，偵測下一個字母是否有在 counter 內出現過。因為 b 還沒出現過，所以記分板上又將 b 加1。<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ePfekJnpovrZhrMWGG3Rwg.png" /></figure>以此類推，下一個動作：<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9FDszVQTDRlp36LskRiQGw.png" /></figure>接著，end 滑動到下一個位置的時候，發現 a 重複出現了：<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*LJgEJjzlVA_CYbDxKNiSOQ.png" /></figure>這時啟動我們的第二個條件，從 counter 中移除 start 所指的元素，並將 start 的位置往前移，縮減 Sliding Window 的範圍。此時代表最長 substring 的變數 max 仍為 3，end 指標再度於原位置偵測這個 Sliding Window 的範圍內，是否有重複的元素：<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cAPgSigCQx5gXStp8L5ckA.png" /></figure>因為沒有重複的，所以 end 又往下移動了一步：<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*lwyDlChYjYLKt_0PH5B_FA.png" /></figure>此時再度發現 Sliding Window 內有重複的元素，於是從 counter 中移除 start 所指的元素，並將 Start 往前移動一步：<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ckjsGr_J6T-fcYgD4PUfAw.png" /></figure>所要寫的迴圈，就是不斷重複這個邏輯，直到 end 的位置移動到等於字串的長度。Max 的值就是我們要輸出的結果。其實 Sliding Window 方法就是利用兩個 pointer，不斷地動態變更字串內的偵測範圍來檢查是否符合條件。轉化成 Code 的話如下：<figure><img alt="" src="https://cdn-images-1.medium.com/max/709/1*Hwhvr6UOg_sGNcCICA6z6w.png" /></figure><blockquote>Object.keys() 會將物件的 key值轉成陣列，利用這個方法來得知物件的長度。</blockquote>如果 console.log(counter) 的話，就看得出 counter 的變化：<figure><img alt="" src="https://cdn-images-1.medium.com/max/231/1*2Oqm7nqYaitcVDP5-0RD9Q.png" /></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=828baf570426" width="1" height="1" alt="">

[Leetcode] 3. Longest Substring Without Repeating Characters

值的拷貝 vs. 參考的拷貝<blockquote>在 Javascript 中，值的型別完全決定了該值是藉由值的拷貝（by value-copy）， 還是藉由參考的拷貝（by reference-copy）來指定的。</blockquote>簡單的值（即純量的的基型值，scalar primitives），永遠都是藉由值的拷貝（value-copy）來指定或傳遞的：像是型別為 null、undefined、string、number、boolean、symbol 的值。下面這個情況，2 是一個純量的基型值，a 持有了該值最初的一份拷貝，b 則被指定了該值的另一份拷貝。這是 by value-copy，所以變更 b 時，並不會動用到 a 的值。<pre>var a = 2;</pre><pre>var b = a;</pre><pre>b++;</pre><pre>console.log(a); //2</pre><pre>console.log(b); //3</pre>複合值的 object (包括 array) 與 function，屬於 by reference-copy。 像下面這個情況，c 跟 d 都是對同一個共有值 [1, 2, 3] 的個別參考。<pre>var c = [1, 2, 3];</pre><pre>var d = c;</pre>所以使用其中任一個參考來修改那個共有的 array 值本身時，影響到的只有那一個共有的值，而兩個參考都會參考到新經過修改的值 [1, 2, 3, 4]。<pre>d.push(4);</pre><pre>console.log(c); //[1, 2, 3, 4]</pre><pre>console.log(d); //[1, 2, 3, 4]</pre>既然參考指向的是共有的值本身，你就無法使用一個參考來變更另一個參考所指向的東西。像我們接著再進行 d= [4, 5, 6] 這個指定時，完全不會影響到 c 所指定的值 [1, 2, 3, 4]<pre>d = [4, 5, 6];</pre><pre>console.log(c); // [1, 2, 3, 4]</pre><pre>console.log(d); // [4, 5, 6]</pre>這種混淆最常發生在函式的參數上：當我們傳入引數 e，會把 e 參考的一個拷貝指定給 x。x 和 e 是指向同一個值 [1, 2, 3] 的不同參考。現在，在函式裡我們可以使用 x 來變動這個值本身。不過我們進行 x = [4, 5, 6] 的指定時，不會影響到 e 所指的這個值。<pre>var e = [1, 2, 3];</pre><pre>function foo(x) {</pre><pre> x.push(4);</pre><pre> console.log(x); // [1, 2, 3, 4]</pre><pre> x = [4, 5, 6];</pre><pre> x.push(7);</pre><pre> console.log(x); //[4, 5, 6, 7]</pre><pre>}</pre><pre>foo(e);</pre><pre>console.log(e); //[1, 2, 3, 4]</pre>如果想要在函式內做修改，讓輸入的陣列最後能呈現 [4, 5, 6, 7] 的值，方法就是去修改函式內的 array。<pre>var f = [1, 2, 3];</pre><pre>function foo2(x) {</pre><pre> x.push(4);</pre><pre> console.log(x); //[1, 2, 3, 4]</pre><pre> x.length = 0; </pre><pre> x.push(4, 5, 6, 7); </pre><pre> console.log(x); //[4, 5, 6, 7]</pre><pre>}</pre><pre>foo2(f);</pre><pre>console.log(f); //[4, 5, 6, 7]</pre>要藉由值的拷貝（by value-copy）傳入一個複合值（像是一個 array），你得手動製作的一份拷貝，讓傳入的參考不會仍然指向原複合值。使用不帶參數的 slice() 預設會製作出 array 的一個全新的（淺層）拷貝，所以我們傳入的參考並不會指向 g 原來指向的值 [1, 2, 3]，g 自然也就沒有被 foo2() 所影響。<pre>var g = [1, 2, 3];</pre><pre>foo2(g.slice()); //這裡沿用上方宣告的 foo2() 函式</pre><pre>console.log(g); //[1, 2, 3]</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7f13e8b11c11" width="1" height="1" alt="">

By Value-Copy vs. By Reference-Copy

<h4>High-Order Function & First-Class Function</h4><h4>First-Class Function 一級函式：</h4>當函式在一個語言中可以被視為變數一樣傳遞時，我們就稱呼那樣的程式語言有「一級函式的特性」。這也是為什麼 Javascript 很適合用來寫 functional programming 的原因。<ol><li>譬如說：可以像這樣將一個匿名函式指派到變數裡，然後在變數後面加上括號來執行這個函式。</li></ol><pre>const foo = function() { console.log("foobar"); } // Invoke it using the variable foo();</pre>2. 也可以把函式當作參數傳入另一個函式之中，並且回傳一個函式。<pre>function doSomething(fn, data) { return fn(data); }</pre><h4>High-Order Function 高階函式</h4>只要是可以接收函式作為參數，或是回傳函式作為輸出的函式，我們就稱為高階函式。例如，JS 裡面很常用的一些對陣列操作的內建API：<ul><li>Array.map( ()⇒{…} )</li><li>Array.filter( ()⇒{…} )</li><li>Array.reduce( ()⇒{…} )</li></ul>以 map() 和 filter() 來舉例的話，其原理簡化後會像是這樣：<figure><img alt="" src="https://cdn-images-1.medium.com/max/657/1*DHMzNNZ-0q4sxkBCqlTxWQ.png" /></figure>這裡透過上面的程式碼實作了高階函式，可以看到的 arrayMap() 和 arrayFilter() 在陣列傳入之後，逐個訪問每個元素並傳入我們自己寫的函式 fn ，這個 fn 會根據我們函式的內容將該值做處理之後回傳。最後透過 Array.push 將我們想要的結果推入新的陣列，然後回傳新的陣列。<img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e722c81f1a01" width="1" height="1" alt="">

高階函式 & 一級函式

原理是先將位置於 i 的數字加入 i-1 個已經排序好的數列，逐一比較後找到其位置，而得到 i 個排序好的數列。再繼續將位置於 i+1 的數字插入這個新排序好的數列，找到其位置。不斷重複這個過程，直到整個數列排序完成。假設有一個如下的陣列我們要由小排到大：<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*58WlmqHRhFpRN1Rn5Ws06g.png" /></figure>綠色是已經排列好的陣列，目前其元素有 4。黃色是我們要拿來做插入的元素。將 1 插入到 4 的陣列中後，發現 1 比 4 小，所以將其位置調換。<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*RwUYrCncec5tvbjvvUc_RA.png" /></figure>綠色是我們經過上述過程得到的，新的排序好的陣列 [ 1, 4 ]。黃色是接著要拿來做插入的元素。將 2 插入到綠色的陣列後，逐一做排序，發現 2 比 4 小，調換其位置；2 再繼續與 1 做比較，2 > 1 ，所以找到其位置，得到排列後的新的綠色陣列 [ 1, 2, 4 ]。<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Um-D4J-rGWhlwCzwDi5Sag.png" /></figure>接著，再拿 5 來做插入，5 跟最右端的元素 4 做比較後發現，5 > 4 ，因為綠色陣列已排序好，自然不用跟前方的元素再做比較，所以得到新的綠色陣列 [1, 2, 4, 5] 。<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XFTSk4HT7xnsc7VFPIQa0g.png" /></figure>重複這樣的過程，就會得到最終排序好的陣列。<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*7JGoLHRlvnW1j7R_H_Fmsw.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*K6PvTyEcQHQmHZRZVzmG4g.png" /></figure>JS 撰寫的程式碼：<figure><img alt="" src="https://cdn-images-1.medium.com/max/888/1*d79HfXHxKM8ftFh9TC84HA.png" /></figure>Worst Case Performance: O(n²)Best Case Performance: O(n)Average Performance: O(n²)<img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d09332f5c7ba" width="1" height="1" alt="">

排序演算法-(2) Insertion Sort

<blockquote>原理就是比較兩兩相鄰的元素，如果彼此在錯誤的順序就將其交換。</blockquote>如下面的例子，從最末端的數字開始兩兩比較的話，較小的數字就好像一個從底部冒起來的泡泡一樣，經過這個過程，慢慢被推擠到前方。<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*6IWtYYYZfgHWa7TTyJEC-w.png" /></figure>直接用實際情況來舉例的話，假設現在有一個如下的陣列：<figure><img alt="" src="https://cdn-images-1.medium.com/max/486/1*JALxQDspIt_HkrLdqEPK3A.png" /></figure><ol><li>外迴圈的 i 會從陣列的第 0 個元素 53 開始，內迴圈的 j 會從陣列的最後一個元素 39 開始。39 跟第 j - 1個元素 28 來做比較的話，是比較大的，所以兩個元素不必互相對調。</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/469/1*n_zArv_i45R_L-ls4ue25A.png" /></figure>2. 這時候我們就將 j 往前移一位到 28 來與它的前一個元素 78 來做比較， 28 是小於 78 的，所以兩個互相對調，此時 j 也往前移動一位。<figure><img alt="" src="https://cdn-images-1.medium.com/max/475/1*ECGwwawUnMbxtf9EBB1byg.png" /></figure>3. 接著，28 與 26 做比較，並沒有比較大。所以陣列元素不變，j 再往前移動一位。<figure><img alt="" src="https://cdn-images-1.medium.com/max/465/1*JNM2hKF-vu0xvkatgdHx7Q.png" /></figure>4. 將 26 與 53 做比較，26 小於 53，兩個元素對調。這時候因為 j 已經抵達 i + 1 的位置，所以結束內迴圈。這樣代表我們已經找到了這個陣列最小的元素且已經將它排列到第一位了！外迴圈的 i 往前移動一個位置。j 又回到最後一個元素的位置，重新啟動一次內迴圈，準備進行和上面相同的比較程序。<figure><img alt="" src="https://cdn-images-1.medium.com/max/461/1*o0HH-_na1phwbyk2xvZFhQ.png" /></figure>5. 接下來的情況就是重複上述的比較程序了。<figure><img alt="" src="https://cdn-images-1.medium.com/max/522/1*IQs_vqxVV_gtc2yc5HF3Kg.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/451/1*SR7WGHHfCF98WJfkYVzfOQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/457/1*7uRMauRcTlWQH6aSgtnxcA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/468/1*E8KJMLa1SO5mO_sLw9f4sg.png" /></figure>完成排序：<figure><img alt="" src="https://cdn-images-1.medium.com/max/491/1*74XPUXOKLl7qrtJ4ZwxSOA.png" /></figure>用 JS 來撰寫的程式碼如下：<figure><img alt="" src="https://cdn-images-1.medium.com/max/559/1*_eXG5bplGXvs9hx5GUwesA.png" /></figure>這裡宣告了一個叫 swapping 的布林值，如果內迴圈 run 完一輪都沒有任何元素調換過位置，代表整個陣列已經過排序，提早結束外迴圈。<blockquote>時間複雜度:</blockquote><blockquote>Worst Case Performance: O(n²)</blockquote><blockquote>Best Case Performance: O(n)</blockquote><blockquote>Average Performance: O(n²)</blockquote>為什麼說 Worst Case 是 O(n²) 呢？假設是這樣的陣列 [n, n-1, n-2, …..4, 3, 2, 1] 來進行 bubble sort— > [1, n, n-1, n-2, …..4, 3, 2] 花費 n-1 步— > [1, 2, n, n-1, n-2, …..4, 3] 花費 n-2 步以此類推，總花費步數就會是:(n-1) + (n-2) + …. + 1 + 0 = (n-1)*n / 2 = n²/2 — n/2因為用到了兩層的迴圈，所以平均的時間複雜度是 O(n²)Best Case 只有在陣列本身幾乎已經接近排序完的狀態。<img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2f4eef0c1091" width="1" height="1" alt="">

排序演算法 - (1) bubble sort

<h3>Hoisting — (2)</h3>接續上一篇，在這邊再用更多例子來對這個主題做一些深入的了解。<pre>console.log(a) //undefined var a = 10</pre>我們知道，在 JavaScript 中程式是一行一行執行的。但是在上方程式碼的情況下，console.log() 的變數 a 卻能夠先被宣告，然後輸出 undefined，這種現象就叫做 Hoisting（提升）。也就是說，當我們宣告一個變數時，宣告本身會被提升至程式碼最上面，而賦值則留在原處，因此也就不會出現 a is not defined 的錯誤。<blockquote>但需注意的是，只有「宣告」會被提升到最上方，但「賦值」不會。</blockquote>若 function 用賦值的方式塞入一個變數內，此時把呼叫寫在 function 前面，則會印出「test is not function」的錯誤：<pre>test();</pre><pre>var test = function() { console.log(123); //TypeError: test is not a function }</pre>那如果同時宣告一個 function 和變數呢？<pre>console.log(b) // [function: b]</pre><pre>var b = 'global'</pre><pre>function b(){ var b = 'local' }</pre><blockquote>function的提升會優先於變數的提升。</blockquote>若是命名重複的函式呢？<pre>function test(){ a(); function a(){ console.log(1); } function a(){ console.log(2); } }</pre><pre>test() //2</pre>會是後面宣告的函式有較高的優先權，所以會印出 2傳入參數到 function 的情況：<pre>function test(a){ console.log(a) //123 var a = 456 console.log(a) //456 }</pre><pre>test(123) </pre>因為 argument 的宣告優先度較高，而且 function 內 var 宣告 a 也只是提升宣告，並未賦值，所以第一次輸出 123，第二次輸出 456那如果同時宣告 function 和 argument 呢？<pre>function test(a){ console.log(a) function a(){ console.log("This is a function inside test");</pre><pre> } }</pre><pre>test(123) //[function a]</pre>function 的宣告會優先於 argument 的宣告，所以會輸出 [function a]但如果是在函式內「宣告變數並賦值」的話，結果就不相同了：<pre>function test(c){ console.log(c) //[function: c] var c = 'hello' console.log(c) //hello</pre><pre> function c(){ console.log(2) } }</pre><pre>test(123)</pre>將上面的 code 想像成經過 hoisting 後如下：<pre>function test(c){ function c(){ //函式宣告提升 console.log(2) } console.log(c) //[function: c]</pre><pre> var c = 'hello' //賦值 console.log(c) //hello }</pre><pre>test(123) </pre>test() 傳入的 argumet 因為優先度較低，而沒有作用。綜合上述幾個例子，可整理出有關 Hoisting 的幾個重點：<blockquote>Hoisting 的優先順序為： 1. 函式宣告（function） 2. 傳進函式的參數（argument） 3. 變數宣告（variable）</blockquote><blockquote>＊只有宣告會提升，賦值不會提升</blockquote>最後一個 較複雜的 exercise 作為例子：<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*CKdPIuAqTmQLqjhttV1VtA.png" /></figure>至於我們為什麼會需要 Hoisting 呢？這個問題其實可以倒過來思考： 「假如沒有 Hoisting 會怎麼樣？」一定要先宣告變數才能使用，養成宣告的好習慣！這樣就不會汙染變數了，感覺還不賴？一定要先宣告函式才能使用，這點其實會造成很大的不便，因為這樣在每個檔案都必須把 function 宣告放在最上面，才能保證底下的程式碼都可以呼叫這些 function，還無法達成 function 間互相呼叫。舉個下面的例子：<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ttMoa7n6ivgD4EpLwCw3Qg.png" /></figure>因為有 Hoisting，我們才能在 loop() 函式中呼叫 logEvenOrOdd()，然後 也在 logEvenOrOdd() 函式中呼叫 loop()。如果沒有 Hoisting，以上的程式碼就不可能達成。因為這牽涉到順序問題，程式只是單純照順序由上到下讀取的話，就沒辦法運用於這種常見的情況。<img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=83c04b2ea166" width="1" height="1" alt="">

Red Chien

Posts from File System

RSS feed on Medium