我担心我在这里遗漏了一些非常明显的东西,但我看不到它。在 chrome 控制台和节点 8.4.0 中运行它,mergeSort 会导致
RangeError: Maximum call stack size exceeded
对于长度大于 1 的输入数组。合并函数似乎工作正常。这是代码:
"use strict";
function merge(A, B) {
if (!Array.isArray(A) || !Array.isArray(B)) {
throw new Error("merge expects both of its arguments to be arrays");
}
let result = [];
let [i, j] = [0, 0];
while (A[i]) {
if (B[j]) {
if (A[i] <= B[j]) {
result.push(A[i]);
i++;
} else {
while (A[i] >= B[j]) {
result.push(B[j]);
j++;
}
result.push(A[i]);
i++;
}
} else {
result.push(A[i]);
i++;
}
}
while (B[j]) {
result.push(B[j]);
j++;
}
return result;
}
function mergeSort(A) {
if (!Array.isArray(A)) {
throw new Error("mergeSort expects its argument to be an array");
}
if (A.length === 1) return A;
let i = A.slice(Math.floor(A.length / 2));
let R = A.slice(i);
let L = A.slice(0, i);
return merge(mergeSort(R), mergeSort(L));
}
最佳答案
i
不应该是一个数组。你只要
let i = Math.floor(A.length / 2);
你的基本情况也太严格了,你的函数也会在空数组上无限递归。
关于javascript - 超出合并排序调用堆栈,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48778481/