RangeError:使用Array.forEach超出最大调用堆栈大小

Question

SRC/QuickSort.js

var quick_sort = function(unsorted) {
  if (unsorted.size <= 1)
    return unsorted;

  var pivot = unsorted.pop();
  var less = new Array();
  var greater = new Array();

  unsorted.forEach(function(element){
    if (element > pivot)
      less.push(element);
    else
      greater.push(element);
  });

  return quick_sort(less) + [pivot] + quick_sort(greater);
};

投机/ QuickSort.js

describe("#quick_sort", function() {

  it("should sort the unsorted array", function() {
    var unsorted = [8, 2, 10, 5, 4, 9, 7, 1, 6, 3];
    var sorted = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    expect(quick_sort(unsorted)).toEqual(sorted);
  });

});

错误信息

RangeError: Maximum call stack size exceeded
    at Array.forEach (native)
    at quick_sort (file://localhost/Users/jasonkim/projects/algorithm-everyday/quick_sort/javascript/src/QuickSort.js:9:12)
    at quick_sort (file://localhost/Users/jasonkim/projects/algorithm-everyday/quick_sort/javascript/src/QuickSort.js:16:10)

我正在尝试使用jasminejs测试快速排序功能.我收到上面的错误.我有终止条件if (unsorted.size <= 1) { return unsorted }.我不确定为什么它不会终止并进入无限循环.

Answer 1

你的问题就在于此

if (unsorted.size <= 1) return unsorted;

因为Arrays没有名为的原型属性size,所以永远不会达到,因此当unsorted空为空时你不会返回Array ,因此进入无限循环,调用quick_sort为空,unsorted直到调用堆栈耗尽为止.

您要查找的属性是Array.prototype.length,如果要将行更改为

if (unsorted.length <= 1) return unsorted;

如果传递空数组,则函数将正确返回.

然而这是一件小事,也可以注意到,

return quick_sort(less) + [pivot] + quick_sort(greater);

如果您希望返回连接的排序数组,则必须更改此行.

你不能简单地使用一个+调用来连接Array ,

[[toPrimitive]]和[[toString]]on lRef并rRef导致数组的串联String表示形式.

这将(因为你是effectivley +"荷兰国际集团所有枢轴阵列,包含单个元素)的类似10987654321,而不是[10,9,8,7,6,5,4,3,2,1]你可能达到的目标.

而是使用Array.prototype.concat哪个连接数组.

return quick_sort(less).concat([pivot]).concat(quick_sort(greater));

这是一个小提琴