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

mergeSort algorithm and memory issue in JavaScript

本文关键字：内存 问题 算法 归并排序 JavaScript      更新时间：2023-09-26

下面是我写的代码:

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中，它不会返回任何结果，在node.js中，它给我

FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - process out of memory Abort trap: 6有人能帮我理解这两个片段之间的区别是什么吗?

提前感谢!

想象一下，你有一个数组left，你做

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

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

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

但是如果你这样做

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

Array.shift() 从数组中删除的第一项，因此在某个点数组的长度将为零，并且循环停止

在进行合并时，您永远不会从第一个元素移动。试试下面的代码:

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);
相关文章：