JavaScript:mergeSort 返回 RangeError:超出最大调用堆栈大小

Question

我目前正尝试在 Javascript 中实现 mergeSort。我收到以下错误:

Users/stevenaguilar/Desktop/algorithms/merge/merge-sort.js:36 sort(a, lo, hi) { ^ RangeError: Maximum call stack size exceeded at Merge.sort (/Users/stevenaguilar/Desktop/algorithms/merge/merge-sort.js:36:7)

输入不是很大，是一个元素，里面有 16 个元素。

a = ["M", "E", "R", "G", "E", "S", "O", "R", "T", "E", "X", "A","M", "P", "L", "E"]

我能够使用 Ruby 创建合并排序并且能够对数组进行排序。不知道为什么我在运行 Node v14.0.0 后使用 JavaScript 会出现上述错误，这里是合并排序的实现:

class Merge {
  constructor() {
    this.aux = []
  }

  sortPublic(a) {
    this.sort(a, 0, a.length - 1);
  }

  merge(a, lo, mid, hi) {
    let i = lo
    let j = hi
    var mid = mid + 1

    for(let k = lo; k <= hi; k++) {
     this.aux[k] = a[k]
    }

    for(let k = lo; k <= hi; k++) {
      if(i > mid) {
        a[k] = this.aux[j++]
      }
      else if(j > hi) {
        a[k] = this.aux[i++]
      }
      else if(this.aux[j] < this.aux[i]) {
        a[k] = this.aux[j++]
      }
      else {
        a[k] = this.aux[i++]
      }
    }

  }

  sort(a, lo, hi) {
    if(lo >= hi) { return; }
    var mid = lo + (lo + hi) / 2
    this.sort(a, lo, mid)
    this.sort(a, mid + 1, hi)
    this.merge(a, lo, mid, hi)
  }
}


let mergeSort = new Merge;
console.log(mergeSort)
let a = ["M", "E", "R", "G", "E", "S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"]

mergeSort.sortPublic(a);

这里有什么问题？

Answer 1

var mid = lo + (lo + hi) / 2有多个问题。如果你想防止溢出，lo + hi是有问题的(正确的公式是 lo + (hi - lo) / 2 )。添加lo回来算了两次。 / 2可能会给出一个 float 结果，这将破坏递归逻辑并作为索引失败。

就设计而言，我认为没有理由让合并排序成为一个有状态类并创建一个实例来对数组进行排序。这是不必要的开销，使调用代码冗长并可能引入错误。制作方法static更有意义，假设你需要一个类(即使这可能是矫枉过正)。

this.aux在多个方法调用和调用之间持续存在很容易出现错误，并且感觉像是过早的优化；使其成为 sort 的纯本地方法提高了可读性、封装性，并确保调用之间没有陈旧数据。是的，为 merge 的每一帧创建一个数组很昂贵，但是如果需要优化，可以将合并数组添加到闭包中或作为参数传递。或者可以进行合并 in place .然后， Array#sort 如果性能是您的目标，这是更好的选择。

我还发现使用传统数组长度协议(protocol)运行所有拆分，其中 lo至 mid包括 lo并且不包括 mid和第二个 block 包括 mid并且不包括 hi更直观。这避免了 mid + 1和 hi - 1并循环 <=我发现这更难推理。

class MergeSorter {
  static merge(a, lo, mid, hi) {
    const sorted = [];
    let i = lo;
    let j = mid;
    
    while (i < mid && j < hi) {
      if (a[i] < a[j]) {
        sorted.push(a[i++]); 
      }
      else {
        sorted.push(a[j++]); 
      }
    }
    
    while (i < mid) sorted.push(a[i++]);
    
    for (let i = 0; i < sorted.length; i++) {
      a[lo++] = sorted[i];
    }
  }

  static sort(a, lo=0, hi=a.length) {
    if (lo < hi - 1) {
      const mid = Math.floor((lo + hi) / 2);
      MergeSorter.sort(a, lo, mid);
      MergeSorter.sort(a, mid, hi);
      MergeSorter.merge(a, lo, mid, hi);
    }
  }
}

const a = [..."MERGESORTEXAMPLE"];
MergeSorter.sort(a);
console.log(a.join(""));

const rnd = n => ~~(Math.random() * n);
let passes = 0;
const tests = 10000;

for (let i = 0; i < tests; i++) {
  const a = Array(rnd(25)).fill().map(() => rnd(25));
  const b = a.slice();
  MergeSorter.sort(a);
  b.sort((a, b) => a - b);

  if ("" + a === "" + b) {
    passes++;
  }
}

console.log(`${passes}/${tests} tests passed`);