JavaScript 中的合并排序算法和内存问题

Question

这是我写的代码：

function mergeSort(array){
    if(array.length < 2) return array;
    var mid = Math.floor(array.length / 2);
    var left = array.slice(0, mid);
    var right = array.slice(mid, array.length);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right){
    var result = [];
    while (left.length && right.length){
        if(left[0]>right[0]){
            result.push(right[0]);
        } else {
            result.push(left[0]);
        }

    }
    while(left.length){
        result.push(left[0]);
    }
    while(right.length){
        result.push(right[0]);
    }
    return result;
}
array = [1000, -94, -115, 300, 22]
mergeSort(array);

以下是我在网上找到的另一个解决方案

    function mergeSort (arr) {
    if (arr.length < 2) return arr;

    var mid = Math.floor(arr.length /2);

    return merge(mergeSort(arr.slice(0,mid)),  mergeSort(arr.slice(mid)));
}

function merge (a,b) {
    var result = [];
    while (a.length >0 && b.length >0)
        result.push(a[0] < b[0]? a.shift() : b.shift());
    return result.concat(a.length? a : b);
}

var test = [-100,3,53,21,4,0];
console.log(mergeSort(test));

相比之下，除了一些语法之外，我找不到任何显着差异。但出于某种原因，我的代码在 chrome 开发控制台和 node.js 环境中都不会运行。在 chrome 中，它不会 return 任何结果，在 node.js 中，它给了我

FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - process out of memory Abort trap: 6 谁能帮我理解这两个真正不同的片段之间的区别是什么？

提前致谢！

Answer 1

想一想，你有一个数组 left 而你做

while(left.length){
    result.push(left[0]);
}

left[0] 不改变数组，它只是获取第一项。

left 的长度 永远不会 改变，你有一个 while 循环，只要数组的长度超过零，它就会继续，并且它总是会的，因为长度永远不会改变。
这是一个无限循环的完美示例，它最终会填满调用堆栈并出现错误，或者在旧版浏览器中只会崩溃。

但是如果你这样做

while(left.length){
    result.push(left.shift());
}

Array.shift() 从数组中删除第一项，因此在某些时候数组长度将为零，循环停止

Answer 2

合并时永远不会离开第一个元素。试试这个代码：

function mergeSort(array){
    if(array.length < 2) return array;
    var mid = Math.floor(array.length / 2);
    var a = array.slice(0, mid);
    var b = array.slice(mid);
    return merge(mergeSort(a), mergeSort(b));
}

function merge(a, b){
    var result = [];
    var i = 0;
    var j = 0;
    while (i < a.length && j < b.length){
        if(a[i] < b[j]){
            result.push(a[i]);
            i++;
        } else {
            result.push(b[j]);
            j++;
        }
    }
    while(i < a.length){
        result.push(a[i]);
        i++;
    }
    while(j < b.length){
        result.push(b[j]);
        j++
    }

    return result;
}

array = [1000, -94, -115, 300, 22];
array = mergeSort(array);
console.log(array);

JavaScript 中的合并排序算法和内存问题

mergeSort algorithm and memory issue in JavaScript

javascript

mergesort

memory-management

v8

node.js