JavaScript中归并排序的案例分析
更新:HHH   时间:2023-1-7


这篇文章将为大家详细讲解有关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 < 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 = 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 < 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 = pide(p, r);
      merge_sort(A, p, q);
      merge_sort(A, q, r);
      merge(A, p, q, r);
    
      return A;
    }

关于JavaScript中归并排序的案例分析就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。

返回web开发教程...