JavaScript中歸併排序的介紹（程式碼範例）

這篇文章帶給大家的內容是關於JavaScript中歸併排序的介紹（程式碼範例），有一定的參考價值，有需要的朋友可以參考一下，希望對你有幫助。

歸併排序（MERGE-SORT）是建立在歸併操作上的一種有效的排序演算法,該演算法是採用分治法（pide andConquer）的一個非常典型的應用。將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合併成一個有序表，稱為二路歸併。

歸併排序

歸併排序是一種非常穩定的排序方法，它的時間複雜度無論是平均，最好，最壞都是NlogN。

歸併排序的2個步驟

1. 先拆分，一直拆分到只有一個數字

2. ##拆分完成之後，開始遞歸合併

拆分過程

#從上圖可以看出，歸併排序會將一個陣列進行兩兩拆分，一直拆分到只有一個數字的時候停止拆分。

那麼拆分的程式碼就很簡單了，就是得到一個指向中間的指標q，將陣列拆分成(start,p)和（p，end）兩個部分。

• p表示陣列的開始下標

• #r表示陣列的結束下標

    function pide(p, r){
        return Math.floor( (p + r) / 2 );
    }

合併過程

合併的過程就如上圖所示

1. 遍歷兩組資料

2. 進行比較大小

3. 較小的那個值取出來放在第一個位置

舉個例子：

• 假設現在數組A的資料是[2,5,1,3]

• 經過我們的分割後會是(0,2),(2,4);

• 我們透過A.slice(0,2)和A.slice(2,4)=>得到兩個數組A1[2,5]和A2[1,3]

• 然後我們對數組[2,5,1,3]進行遍歷，第一次會得到兩邊較小的數1，第二次2，第三次3，第四次是5

    function merge(A, p, q, r){
        const A1 = A.slice(p, q);
        const A2 = A.slice(q, r);
        
        // 哨兵，往A1和A2里push一个最大值，比如防止A1里的数都比较小，导致第三次遍历某个数组里没有值
        
        A1.push(Number.MAX_SAFE_INTEGER);
        A2.push(Number.MAX_SAFE_INTEGER);
        // 循环做比较，每次取出较小的那个值
        for (let i = p, j = 0, k = 0; i 主程式<h3></h3>主程式就是做遞歸重複上面的操作了<p></p><pre class="brush:php;toolbar:false">    function merge_sort(A, p = 0, r) {
      r = r || A.length;
      if (r - p === 1) {
        return;
      }
      const q = pide(p, r);
      merge_sort(A, p, q);
      merge_sort(A, q, r);
      merge(A, p, q, r);
    
      return A;
    }

完整程式碼

    function pide(p, r) {
      return Math.floor((p + r) / 2);
    }
    
    function merge(A, p, q, r) {
      const A1 = A.slice(p, q);
      const A2 = A.slice(q, r);
      A1.push(Number.MAX_SAFE_INTEGER);
      A2.push(Number.MAX_SAFE_INTEGER);
    
      for (let i = p, j = 0, k = 0; i 

#

以上是JavaScript中歸併排序的介紹（程式碼範例）的詳細內容。更多資訊請關注PHP中文網其他相關文章！