js算法-歸并排序（merge_sort）

stormjun 發布于2019-08-23 14:37 / 2130人閱讀

摘要：歸并排序是建立在歸并操作上的一種有效的排序算法該算法是采用分治法的一個非常典型的應用。若將兩個有序表合并成一個有序表，稱為二路歸并。歸并排序歸并排序是一種非常穩定的排序方法，它的時間復雜度無論是平均，最好，最壞都是。

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

歸并排序

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

歸并排序的2個步驟

先拆分，一直拆分到只有一個數

拆分完成后，開始遞歸合并

拆分過程

從上圖可以看出，歸并排序會將一個數組進行兩兩拆分，一直拆分到只有一個數的時候停止拆分。
那么拆分的代碼就很簡單了，就是得到一個指向中間的指針q，將數組拆分成(start,p)和（p，end）兩個部分。

p表示數組的開始下標

r表示數組的結束下標

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

合并過程

合并的過程就如上圖所示

遍歷兩組數據

進行對比大小

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

舉個例子：

假設現在數組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 < r; i++) {
            if (A1[j] < A2[k]) {
              A[i] = A1[j];
              j++;
            } else {
              A[i] = A2[k];
              k++;
            }
         }
    }

主程序

主程序就是做遞歸重復上面的操作了

    function merge_sort(A, p = 0, r) {
      r = r || A.length;
      if (r - p === 1) {
        return;
      }
      const q = divide(p, r);
      merge_sort(A, p, q);
      merge_sort(A, q, r);
      merge(A, p, q, r);
    
      return A;
    }

完整代碼

    function divide(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 < r; i++) {
        if (A1[j] < A2[k]) {
          A[i] = A1[j];
          j++;
        } else {
          A[i] = A2[k];
          k++;
        }
      }
    }
    
    function merge_sort(A, p = 0, r) {
      r = r || A.length;
      if (r - p === 1) {
        return;
      }
      const q = divide(p, r);
      merge_sort(A, p, q);
      merge_sort(A, q, r);
      merge(A, p, q, r);
    
      return A;
    }

推薦閱讀

數據結構系列：
js數據結構-棧
js數據結構-鏈表
js數據結構-隊列
js數據結構-二叉樹（二叉堆）
js數據結構-二叉樹（二叉搜索樹）
js數據結構-散列表(哈希表)

云服務器 GPU云服務器歸并排序算法 js 歸并排序歸并排序二路歸并排序

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/100887.html

數據結構與算法——希爾、歸并、快速排序

摘要：今天再來看看另外三種時間復雜度都是的排序算法，分別是希爾排序歸并排序和快速排序。三數取中法求將放到數組的末尾總結這三種排序算法的平均時間復雜度都是，歸并排序和快速排序的應用更廣泛。 1. 回顧前面說完了三種較為簡單的排序算法，分別是冒泡排序，選擇排序和插入排序，它們的平均情況時間復雜度都是 O(n2)，比較的高，適合小規模的數據排序，其中插入排序的效率稍高，所以更推薦使用插入排序。今...

hersion 2019-08-16 15:58 評論0 收藏0
各種排序算法總結

摘要：排序算法是最基本最常用的算法，不同的排序算法在不同的場景或應用中會有不同的表現，我們需要對各種排序算法熟練才能將它們應用到實際當中，才能更好地發揮它們的優勢。今天，來總結下各種排序算法。排序算法是最基本最常用的算法，不同的排序算法在不同的場景或應用中會有不同的表現，我們需要對各種排序算法熟練才能將它們應用到實際當中，才能更好地發揮它們的優勢。今天，來總結下各種排序算法。下面這個表格...

null1145 2019-08-19 10:23 評論0 收藏0
php插入排序,快速排序,歸并排序,堆排序

摘要：的陣列視為基本型別，所以必須用傳參考才能修改原陣列插入排序快速排序歸并排序堆排序獲取個數處理一半的數據 function bubble_sort(&$arr) {//php的陣列視為基本型別，所以必須用傳參考才能修改原陣列 for ($i = 0; $i < count($arr) - 1; $i++) for ($j = 0; $j < count($arr)...

JerryZou 2019-07-01 10:12 評論0 收藏0
基本排序算法的Python實現

摘要：本篇主要實現九八大排序算法，分別是冒泡排序，插入排序，選擇排序，希爾排序，歸并排序，快速排序，堆排序計數排序。希爾排序是非穩定排序算法。歸并排序算法依賴歸并操作。但是，計數排序可以用在基數排序算法中，能夠更有效的排序數據范圍很大的數組。本篇主要實現九(八）大排序算法，分別是冒泡排序，插入排序，選擇排序，希爾排序，歸并排序，快速排序，堆排序,計數排序。希望大家回顧知識的時候也能從我的這...

zhangqh 2019-07-25 10:42 評論0 收藏0
八大排序算法使用python實現

摘要：創建最大堆堆排序八計數排序以上節選自維基百科代碼如下為數組中的最大值待排序數組長度設置輸出序列，初始化為設置技術序列，初始化為本文章參考維基百科和八大排序算法實現合輯一、冒泡排序冒泡排序算法的運作如下：比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。這步做完后，最后的元素會是最大的數。針對所有的元素重復以上的步驟，...

meislzhua 2019-07-31 11:23 評論0 收藏0