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

Question

我目前正在尝试在 Javascript 中实现 mergeSort。我收到以下错误：用户/stevenaguilar/Desktop/algorithms/merge/merge-sort.js:36 sort(a, lo, hi) { ^ RangeError: 最大调用堆栈大小在 Merge.sort (/Users/stevenaguilar/Desktop/algorithms/merge/合并-sort.js:36:7)输入不是那么大，是一个包含 16 个元素的元素。a = ["M", "E", "R", "G", "E", "S", "O", "R", "T", "E", "X", "A","M", "P", "L", "E"]我能够使用 Ruby 创建合并排序，并且能够对数组进行排序。不知道为什么我在 JavaScript 中遇到上述错误，因为我在Node  v14.0.0 这里运行的是合并排序的实现：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可能会给出一个浮点结果，这将破坏递归逻辑并作为索引失败。

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

this.aux在多个方法调用和调用之间持续存在错误已经成熟，感觉就像过早的优化；将其完全设置为sort方法的本地可以提高可读性、封装性并确保在调用之间没有陈旧的数据存在。是的，为每一帧创建一个数组merge很昂贵，但是如果需要优化，可以将合并数组添加到闭包中或作为参数传递。或者合并可以就地完成。再说一次，Array#sort如果性能是您的目标，这是更好的选择。

我还发现，使用传统的数组长度协议运行所有拆分，其中lo包含mid和lo不包含以及包含和不mid包含的第二个块更直观。这避免了我觉得更难推理的和循环。midhimid + 1hi - 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`);