归并排序JavaScript实现_关于归并排序思路和代码实现

归并排序：其基本思想是分治策略，先进行划分，然后再进行合并。那么步骤如下: 

1.我们以数组[1, 5, 6, 2, 4, 3]举例，归并排序的第一步，将数组一分为2：

[1, 5, 6] [2, 4, 3]

2.接着将分成的数组继续一分为2，直到长度为1，我们构成如下二叉树（成树 从上往下）：

[1, 5, 6, 2, 4, 3]
       /                 \
[1, 5, 6]             [2, 4, 3]
/       \            /         \
[1]    [5, 6]      [2]       [4, 3]
       /    \                /    \
      [5]   [6]             [4]   [3]

3.当递归到了尽头，我们向上回溯，对于两个有序的数组，我们将它们合并成一个有序数组，从而完成整个归并排序（归并 从下往上）：

[1, 2, 3, 4, 5, 6]
       /                 \
[1, 5, 6]             [2, 3, 4]
/       \            /         \
[1]    [5, 6]      [2]       [3, 4]
       /    \                /    \
      [5]   [6]             [4]   [3]

直接上代码：  

function merge(left, right) {
  var tmp = [];

  while (left.length && right.length) {
    if (left[0] < right[0])
      tmp.push(left.shift());
    else
      tmp.push(right.shift());
  }

  return tmp.concat(left, right);
}

function mergeSort(a) {
  if (a.length === 1) 
    return a;

  var mid = ~~(a.length / 2)
    , left = a.slice(0, mid)
    , right = a.slice(mid);

  return merge(mergeSort(left), mergeSort(right));
}

这段合并排序的代码相当简单直观，但是mergeSort()函数会导致很频繁的自调用。一个长度为n的数组最终会调用mergeSort() 2*n-1次，这意味着如果需要排序的数组长度很大会在某些栈小的浏览器上发生栈溢出错误。

这里插个话题，关于递归调用时浏览器的栈大小限制，可以用代码去测试：

var cnt = 0;
try {
  (function() {
    cnt++;
    arguments.callee();
  })();
} catch(e) {
  console.log(e.message, cnt);
}

遇到栈溢出错误并不一定要修改整个算法，只是表明递归不是最好的实现方式。这个合并排序算法同样可以迭代实现，比如（摘抄自《高性能JavaScript》）： 

function merge(left, right) {
  var result = [];

  while (left.length && right.length) {
    if (left[0] < right[0])
      result.push(left.shift());
    else
      result.push(right.shift());
  }

  return result.concat(left, right);
}

function mergeSort(a) {
  if (a.length === 1)
    return a;

  var work = [];
  for (var i = 0, len = a.length; i < len; i++)
    work.push([a[i]]);

  work.push([]); // 如果数组长度为奇数

  for (var lim = len; lim > 1; lim = ~~((lim + 1) / 2)) {
    for (var j = 0, k = 0; k < lim; j++, k += 2) 
      work[j] = merge(work[k], work[k + 1]);

    work[j] = []; // 如果数组长度为奇数
  }

  return work[0];
}

console.log(mergeSort([1, 3, 4, 2, 5, 0, 8, 10, 4]));

这个版本的mergeSort()函数功能与前例相同却没有使用递归。尽管迭代版本的合并排序算法比递归实现要慢一些，但它并不会像递归版本那样受调用栈限制的影响。把递归算法改用迭代实现是实现栈溢出错误的方法之一。  

本文内容仅供个人学习、研究或参考使用，不构成任何形式的决策建议、专业指导或法律依据。未经授权，禁止任何单位或个人以商业售卖、虚假宣传、侵权传播等非学习研究目的使用本文内容。如需分享或转载，请保留原文来源信息，不得篡改、删减内容或侵犯相关权益。感谢您的理解与支持！

链接: https://shenqiku.cn/article/FLY_387