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

Question

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

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 中有两个问题。正确的写法是这样的：

1 2 3 4 5 6 7 8 9 10

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

  非常感谢！