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 } 上面的终止条件。我不确定为什么它没有终止并进入无限循环。

最佳答案

你的问题是线路
if (unsorted.size <= 1) return unsorted;
由于数组没有名为 size 的原型(prototype)属性,因此永远不会达到,
因此,当 unsorted 为空并因此进入无限循环时,您不会返回数组,使用空的 quick_sort 调用 unsorted 直到调用堆栈耗尽。

您正在寻找的属性是 Array.prototype.length ,如果您将该行更改为
if (unsorted.length <= 1) return unsorted;
如果它传递了一个空数组,您的函数将正确返回。

不过有一点也可以注意到,
return quick_sort(less) + [pivot] + quick_sort(greater);
如果您希望返回一个串联的排序数组,您也必须更改此行。

您不能简单地使用 + 运算符连接 Array,该运算符调用,
[[toPrimitive]][[toString]] 上的 lRefrRef 导致数组的串联字符串表示。

这将(因为您是 + 'ing 所有枢轴数组,包含单个元素)在 10987654321 之类的东西中,而不是 [10,9,8,7,6,5,4,3,2,1] 您可能实现的目标。

而是使用连接数组的 Array.prototype.concat
return quick_sort(less).concat([pivot]).concat(quick_sort(greater));
这是一个 Fiddle

关于javascript - RangeError : Maximum call stack size exceeded using Array. forEach,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/18180905/

10-09 15:00