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);
};
spec/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);
如果您希望返回一个串联的排序数组,您也必须更改这一行。
您不能简单地使用 +
连接数组运营商,调用,
[[toPrimitive]]
和 [[toString]]
在 lRef
和 rRef
导致数组的串联 String 表示形式。
这会(因为你是有效的 +
'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/