javascript - 使用 mergesort 计算反转 - javascript

Question

下面的代码统计了编号。数组中的反转。它总是递归地分成子问题，直到出现堆栈错误 RangeError: Maximum call stack size exceeded 即使定义了基本情况也会发生。这里可能是什么问题

function mergeSort(arr) {
    var n = arr.length;
    var l=0,h=n-1;
    if (l<h) {
        var m=findMid(l,h);
        var leftArr=arr.slice(l,m);
        var rightArr=arr.slice(m,n);
        var invCount = mergeSort(leftArr)+mergeSort(rightArr);
        invCount += merge(leftArr,rightArr,n);
    }
    return invCount;
}

function merge(a, b,n) {
    var i=0,j=0,m=[];
    var splitInv=0;
    for(var k=0;k<n;k++) {
        if(a[i]<b[j]) m[k]=a[i++];
        else if (b[j]<a[i]){
            m[k]=b[j++];
            splitInv+=n-i;
        }
    }
    return splitInv;
}
function findMid(l, r) {
    var m = Math.floor((l + r) / 2);
    return m;
}

我修改了上面的代码，以不同的方式处理基本情况。以下逻辑是否正确:

function mergeSort(arr) {
    var n = arr.length;
    var l=0,h=n-1;
    var invCount=0;
    if(n<=2) {
        return merge(arr[0],arr[1],n);
    }else{
        var m=Math.floor(n/2);
        var leftArr=arr.slice(l,m);
        var rightArr=arr.slice(m);
        invCount += mergeSort(leftArr)+mergeSort(rightArr);
    }
    return invCount;
}

function merge(a, b,n) {
    var i=0,j=0,m=[];
    var splitInv=0;
    if(typeof b=="undefined") {
        return 0;
    }
    for(var k=0;k<n;k++) {
        if(a[i]<b[j]) m[k]=a[i++];
        else if (b[j]<a[i]){
            m[k]=b[j++];
            splitInv+=n-i;
        }
    }
    return splitInv;
}

Answer 1

RangeError 由于对 mergeSort 的递归调用过多而出现。 对于 arr 2 的大小，rightArr 的大小将保持为 2。 代替 var rightArr=arr.slice(m,n); 你可以做 var rightArr=arr.slice(m+1,n);