用 JavaScript 學習資料結構和演算法：排序（Sort）與搜尋（Search）篇

   <p style="text-align:center"><img src="https://simg.open-open.com/show/88d736e883f47731ac65e6b2b5ad4db5.png"></p>    <h2><strong>什麼是排序（Sort）？</strong></h2>    <p>想像一下如果你今天因為牙齒疼，想找住家附近的牙醫診所（假設你沒有網路和查號台可以使用），你必須得翻開電話黃頁一個個找。若是這本黃頁好死不死沒有做任何排序的話，你可能需要從頭到尾一個個查看，當然故事的結局很可能是等你找到電話時你已經疼死在家裡了。所以說選擇合適的排序方式讓資料更有組織和有效率地編排是排序演算法的目標。以下就介紹幾個經典的排序演算法，再介紹排序演算法之前，我們先建立一個陣列類別方便表示排序和搜尋的資料。</p>    <pre>  <code class="language-javascript">function ArrayList() {   let array = [];   this.insert = function() {    array.push(item);   };   // 方便輸出結果   this.toString() = function() {    return array.join();   };  }  </code></pre>    <h2><strong>氣泡排序法（Bubble Sort）</strong></h2>    <p style="text-align:center"><img src="https://simg.open-open.com/show/a42a794615876ef751aa1d7280f53760.png"></p>    <p>雖然氣泡排序法是所有排序演算法中效能最差的，但卻也是最簡單的演算法，所以我們首先來介紹氣泡排序法：</p>    <ol>     <li> <p>實作氣泡排序法：氣泡排序法核心觀念為比較任兩個相鄰項目，如果第一個比第二個大，則交換兩個數字，重複進行比較到最後。元素會如同氣泡一樣從水裡往上浮至正確位置。</p> <pre>  <code class="language-javascript">this.bubbleSort = function() {   let length = array.length;   for(let i; i < length; i++) {    // 比到後來最後一位已經排序好    for(let j = 0; j < length - 1; j++) {     if(array[j] > array[j + 1]) {      swap(j, j + 1);     }    }   }  };    const swap = function(index1, index2) {   let tmp = array[index1];   array[index1] = array[index2];   array[index2] = tmp;  }  </code></pre> <p>測試程式碼：</p> <pre>  <code class="language-javascript">function createNonSortedArray(size) {   let array = new ArrayList();   for(let i = size; i > 0; i--) {    array.insert(i);   }   return array;  }    let array = createNonSortedArray(5);  array.bubbleSort();  console.log(array.toString);  </code></pre> </li>     <li> <p>改進後的氣泡排序法：如果修改成內圈減外圈的輪數，可以避免不必要的比較。同時也加上 flag 記錄交換情形：</p> <pre>  <code class="language-javascript">this.bubbleSort = function(data){      var flag = true;      for(var i = 0; i < data.length - 1 && flag; i++){          flag = false;          for(var j = 0; j < data.length - i - 1; j++){              if(data[j+1] < data[j]){                  swap(data, j+1, j);                  flag = true;              }          }      }  };  </code></pre> </li>     <li> <p>時間複雜度（Time Complexity）</p>      <ul>       <li> <p>Best Case：Ο(n)</p> <p>當資料的順序恰好為由小到大時</p> <p>第一次執行後，未進行任何swap ⇒ 提前結束</p> </li>       <li> <p>Worst Case：Ο(n2)</p> <p>當資料的順序恰好為由大到小時</p> <p>每回合分別執行：n-1、n-2、…、1次</p> <p>(n-1) + (n-2) + … + 1 = n(n-1)/2 ⇒ Ο(n2)</p> </li>       <li> <p>Average Case：Ο(n2)</p> <p>第n筆資料，平均比較 (n-1)/2 次</p> </li>      </ul> </li>     <li> <p>空間複雜度（Space Complexity）：θ(1)</p> </li>    </ol>    <h2><strong>選擇排序法（Selection Sort）</strong></h2>    <p style="text-align:center"><img src="https://simg.open-open.com/show/83232439c2dace2766ebd00cec9f59ae.jpg"></p>    <ol>     <li> <p>實作選擇排序法（Selection Sort）：選擇排序法的主要思路在於每次選擇資料結構中最小值放到第一位，再找第二小放到第二位，依此類推。</p> <pre>  <code class="language-javascript">this.selectionSort = function() {   let length = array.length;   let indexMin;   for(let i = 0; i < length - 1; i++) {    indexMin = i;    for(let j = i; j = length; j++) {     if(array[indexMin] > array[j]) {      // 找未排序中最小值      indexMin = j;     }    }    if(i !== indexMin) {     swap(i, indexMin);    }   }  };  </code></pre> </li>     <li> <p>使用選擇排序：</p> <pre>  <code class="language-javascript">array = createNonSortedArray(5);  console.log(array.toString());  array.selectionSort();  console.log(array.toString());  </code></pre> </li>     <li> <p>時間複雜度（Time Complexity）</p>      <ul>       <li> <p>Best Case：Ο(n2)</p> </li>       <li> <p>Worst Case：Ο(n2)</p> </li>       <li> <p>Average Case：Ο(n2)</p> <p>說明：無論資料順序如何，都會執行兩個迴圈</p> </li>      </ul> </li>     <li> <p>空間複雜度（Space Complexity）：θ(1)</p> </li>    </ol>    <h2>插入排序法（Insertion Sort）</h2>    <p style="text-align:center"><img src="https://simg.open-open.com/show/cb2ffd4e3c9070b4e787767c83a157b8.png"></p>    <ol>     <li> <p>實作插入排序法（Insertion Sort）</p> <pre>  <code class="language-javascript">this.insertionSort = function() {   let length = array.length;   let j;   let temp;   for(let i = 1; i < length; i++) {    j = i;    temp = array[i];    while(j > 0 && array[j - 1] > temp) {     array[j] = array[j - 1];     j--;    }    array[j] = temp;   }  };  </code></pre> </li>     <li> <p>使用插入排序法（Insertion Sort）</p> </li>     <li> <p>時間複雜度(Time Complexity)</p>      <ul>       <li> <p>Best Case：Ο(1)</p> <p>當資料的順序恰好為由小到大時，每回合只需比較1次</p> </li>       <li> <p>Worst Case：Ο(n2)</p> <p>當資料的順序恰好為由大到小時，第i回合需比i次</p> </li>       <li> <p>Average Case：Ο(n2)</p> <p>第n筆資料，平均比較n/2次</p> </li>      </ul> </li>     <li> <p>空間複雜度(Space Complexity)：θ(1)</p> </li>    </ol>    <h2><strong>合併排序法（Merge Sort）</strong></h2>    <p style="text-align:center"><img src="https://simg.open-open.com/show/d9b248f2e3ede641b6ba88e277dc399b.png"></p>    <p>前面三個介紹的演算法由於效能不佳比較少能實際使用在真實狀況，但合併排序法的效能不錯，在瀏覽器支援實作的 JavaScript 中就有使用到合併排序法（Merge Sort）。</p>    <ol>     <li> <p>實作合併排序法（Merge Sort）：合併演算法是一種分治型演算法，主要思想是將原始陣列切分成較小陣列，直到每個小陣列只有一個位置，接著將小陣列合併成較大陣列，直到最後只有一個排序完畢的大陣列，在合併排序法中我們必須使用遞迴的觀念。</p> <pre>  <code class="language-javascript">this.mergeSort = function() {   array = mergeSortRec(array);  }    const mergeSortRec = function(array) {   const length = array.length;   if(length === 1) {    return array;   }   const mid = Math.floor(length / 2);   const left = array.slice(0, mid);   const right = array.slice(mid, length);   return merge(mergeSortRec(left), mergeSortRec(right));  }  </code></pre> </li>     <li> <p>使用合併排序法（Merge Sort）</p> <pre>  <code class="language-javascript">const merge = function(left, right) {   const result = [];   let il = 0;   let ir = 0;   while(il < left.length && ir < right.length) {    if(left[il] < right[ir]) {     result.push(left[il++]);    } else {     result.push(right[ir++]);    }   }     while(il < left.length) {    result.push(left[il++]);   }     while(ir < right.length) {    result.push(right[ir++]);   }     return result;  };  </code></pre> </li>     <li> <p>時間複雜度（Time Complexity）</p>      <ul>       <li> <p>Best Case：Ο(n log n)</p> </li>       <li> <p>Worst Case：Ο(n log n)</p> </li>       <li> <p>Average Case：Ο(n log n)</p> <p>T(n) = MergeSort（左子數列） + MergeSort（右子數列）+ Merge</p> <p>= T(n/2) + T(n/2) + c×n = O(n log2n)</p> </li>      </ul> </li>     <li> <p>空間複雜度（Space Complexity）：Ο(n)</p> <p>因為需要暫時性的暫列存放每回合合併後的結果</p> </li>    </ol>    <h2><strong>快速排序法（Quick Sort）</strong></h2>    <p style="text-align:center"><img src="https://simg.open-open.com/show/0ed1fa7c47418685069e3056b9d27ca4.png"></p>    <ol>     <li> <p>實作快速排序法（Quick Sort）：快速排序法是最常用的排序法之一，其複雜度為 O(nlogn)，且效能也比其他複雜度相同的排序法好。快速排序法主要採取分割與征服（Divide and Conquer）的策略，其主要思路也是將原始陣列分為較小陣列來處理。在實作上，首先我們先從陣列中選擇中間一項作為基準值（pivot）。接下來建立兩個指位器一個指到開頭，若數值小於基準值則指標往前，另外一個指到結尾，當值大於基準值時指針往左移動。接著演算法對劃分後的小陣列重複之前的兩步驟，直到陣列完全排列。</p> <pre>  <code class="language-javascript">this.quickSort = function() {   quick(array, 0, array.length - 1);  };    const quick = function(array, left, right) {   let index;   if(array.length > 1) {    index = partition(array, left, right);   }   };    // 實作劃分過程  const partition = function(array, left, right) {   const pivot = array[Math.floor((right + left) / 2)];   const i = left;   const j = right;   while(i <= j) {    while(array[i] < pivot) {     i++;    }    while(array[j] > pivot) {     j++;    }    if(i <= j) {     swapQuickSort(array, i, j);     i++;     j--;    }   }   return i;  }    const swapQuickSort = function(array, index1, index2) {   const tmp = array[index1];   array[index1] = array[index2];   array[index2] = tmp;  }  </code></pre> </li>     <li> <p>使用快速排序法（Quick Sort）</p> <pre>  <code class="language-javascript">array = createNonSortedArray(5);  array.quickSort();  </code></pre> </li>     <li> <p>時間複雜度(Time Complexity)</p>      <ul>       <li> <p>Best Case：Ο(n log n)</p> <p>第一個基準值的位置剛好是中位數，將資料均分成二等份</p> </li>       <li> <p>Worst Case：Ο(n2)</p> <p>當資料的順序恰好為由大到小或由小到大時，此時有分割跟沒分割一樣</p> </li>       <li> <p>Average Case：Ο(n log n)</p> </li>      </ul> </li>     <li> <p>空間複雜度(Space Complexity)：Ο(log n) ~ Ο(n)</p> <p>快速排序法的空間複雜度會依實作方式而有所不同</p> <p>因為遞迴呼叫需要額外的堆疊空間 ⇒ 複雜度會因遞迴的深度而異</p>      <ul>       <li> <p>Best Case： Ο(log n)</p> <p>遞迴呼叫的深度為 log n</p> </li>       <li> <p>Worst Case： Ο(n)</p> <p>遞迴呼叫的深度為 n-1</p> </li>      </ul> </li>    </ol>    <h2><strong>什麼是搜尋（Search）？</strong></h2>    <p>搜尋是為了要在資料結構中找到想要的元素。</p>    <h2><strong>循序搜尋（Sequential Search）</strong></h2>    <pre>  <code class="language-javascript">this.sequentialSearch = function(item) {   for(let i = 0; i < array.legth; i++) {    if(item === array[i]) {     return i;    }   }   return -1;  };  </code></pre>    <h2><strong>二分搜尋（Binary Search）</strong></h2>    <ol>     <li>先做排序，我們這邊使用快速排序</li>     <li>選擇中間值</li>     <li>如果選取值是要搜尋值則結束搜尋</li>     <li>如果待搜尋值比選取值小，則返回步驟一在選取值左邊子陣列中尋找</li>     <li>如果待搜尋值比選取值大，則返回步驟一在選取值右邊子陣列中尋找</li>    </ol>    <pre>  <code class="language-javascript">this.binarySearch = function() {   this.quickSort();   let low = 0;   let high = array.length;   let mid;   let element;   while(low <= high) {    mid = Math.floor((low + high) / 2);    element = array[mid];    if(element < item) {     low = mid + 1;    } else if (element > item) {     high = mid - 1;    } else {     return mid;    }   }   return -1;  };  </code></pre>    <h2><strong>總結</strong></h2>    <p>在這個單元中我們學習了演算法中幾種經典的排序：</p>    <ol>     <li>氣泡排序法（Bubble Sort）</li>     <li>選擇排序法（Selection Sort）</li>     <li>插入排序法（Insertion Sort）</li>     <li>合併排序法（Merge Sort）</li>     <li>快速排序法（Quick Sort）</li>    </ol>    <p>以及搜尋方法：</p>    <ol>     <li>循序搜尋（Sequential Search）</li>     <li>二分搜尋（Binary Search）</li>    </ol>    <p> </p>    <p>来自：http://blog.kdchang.cc/2016/09/27/javascript-data-structure-algorithm-sort-and-search/</p>    <p> </p>