实在找不出问题了，报错RangeError: Maximum call stack size exceeded

Question

function generateRandomArray(n,l,r) {
    arr = new Array(n);
    for(let i = 0; i<n;i++){
        arr[i] = Math.floor(Math.random()*(r-l))+l;
    }
    return arr;
}
function fntime(fn) {
    let start = new Date().getTime(); // 开始时间
    fn()
    let end = new Date().getTime(); // 结束时间
    console.log(end - start+"毫秒！");
}
var arr = [];
function guibing() {
    _gui(arr,0,arr.length-1);
}
function _gui(arr,l,r) {
    if(l >= r){
        return;
    }
    let mid = Math.ceil((r+l)/2);
    _gui(arr,l,mid);
    _gui(arr,mid,r);
    _merge(arr,l,mid,r);
    console.log("我是归并排序"+arr);
}
function _merge (arr,l,mid,r) {
    let aux = [];
    for (let i=l; i<=r; i++){
        aux[i-l] = arr[i]
    }
    let i = l;
    let j = mid + 1;
    for (let k = l;k <= r; k++){
        if(i>mid){
            arr[k] = aux[j-l];
            j++
        }else if(j>r) {
            arr[k] = aux[i-l];
            i++
        }
        else if(aux[i-l]<aux[j-l]){
            arr[k] = aux[i-l];
            i++
        }else {
            arr[k] = aux[j-l];
            j++
        }
    }
}
function main() {
    generateRandomArray(10,0,5000)
    fntime(guibing)
}
main()

Answer 1

liuyubobobo 2017-02-17 23:25:24

在 _gui 中有两个问题。正确的写法是这样的：

function _gui(arr,l,r) {
    if(l >= r){
        return;
    }
    let mid = Math.floor((r+l)/2);
    _gui(arr,l,mid);
    _gui(arr,mid+1,r);
    _merge(arr,l,mid,r);
    console.log("我是归并排序"+arr);
}

1. 第二次递归调用，应该是 _gui(arr,mid+1,r);因为mid位置的元素在上一行_gui(arr,l,mid)中已经被处理了。
   

2. mid的计算，需要下取整，上取整是不行的。这个问题比较tricky。你可以设想一下，对于区间[0,1]，当l=0；r=1的时候，mid如果做上取整，结果仍然为1，我们将整个数组分成了[0,1]和[]（空数组）两部分，就陷入了一个无穷的循环。但是做下取整，mid=0，区间[0,1]就被分成了[0,0]和[1,1]两部分。

解决算法问题要有耐心，出现问题要做调试。调试不是盯着代码看，是要尝试输出代码中的关键数值，进而观察代码的运转；要自己设计小的数据用例做测试。调试是程序是做开发的基本功。可以说，在实际开发中，有90%的时间都是在做调试的。所以，一定要有耐心啊。

加油！

• 提问者 拖车板牙爵士 #1

  非常感谢！