js算法-归并排序（merge_sort）

stormjun 发布于2019-08-23 14:37 / 2127人阅读

摘要：归并排序是建立在归并操作上的一种有效的排序算法该算法是采用分治法的一个非常典型的应用。若将两个有序表合并成一个有序表，称为二路归并。归并排序归并排序是一种非常稳定的排序方法，它的时间复杂度无论是平均，最好，最坏都是。

归并排序（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 归并排序归并排序二路归并排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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