JS归并排序函数内存不足

Question

我试图使用 pop() 改进典型合并排序函数的时间。当我运行它在 Chrome 时，它因内存错误而崩溃。显然这意味着它在没有完成的情况下循环，但我不知道为什么。

代码如下：

function mergeSorted(a, b){
  var c = [];
  while(a.length && b.length){
    var a1 = a.pop();
    var b1 = b.pop();
    var aIndex = parseInt((a.length) - 1);
    var bIndex = parseInt((b.length) - 1);
    while(b[bIndex] >= a[aIndex]) c.push(b1);
    while(a[aIndex] >= b[bIndex]) c.push(a1);
  }
  return c;
}

var a = [1, 3, 5, 7, 7, 8, 8, 9, 9];
var b = [2, 4, 5, 6, 7, 8, 9];
mergeSorted(a, b);

Answer 1

你的最后两个 while 循环应该是 if 条件，因为你没有在循环内部改变任何 while 循环条件，所以会无限循环。

if(b[bIndex] >= a[aIndex]) c.push(b1);
if(a[aIndex] >= b[bIndex]) c.push(a1);

JS归并排序函数内存不足

JS merge sort function runs out of memory

javascript

arrays

sorting

mergesort