javascript - JS快速排序算法去掉判断就报错？-PHP中文网问答

var arr = [111,2,311,'a',20,90,445];

    var quickSort = function(arr) {　　
    if (arr.length <= 1) {
        return arr;
    } else {
        //split for center 
        var pivotIndex = Math.floor(arr.length / 2);

        //get center value
        var pivot = arr.splice(pivotIndex, 1)[0];
          console.log(pivot)
        var left = [];　　
            var right = [];
        for (var i = 0; i < arr.length; i++) {
            if (arr[i] < pivot) {
                left.push(arr[i]);
            } else {
                    right.push(arr[i]);
            }
         }
     }
    //call me loop
    return quickSort(left).concat([pivot], quickSort(right));
};

    console.log(quickSort(arr));
这样是可以运行的，但是删掉判断数组长度那一段就报错

var arr = [111, 2, 311, 'a', 20, 90, 445];

var quickSort = function(arr) {　　

    //split for center 
    var pivotIndex = Math.floor(arr.length / 2);

    //get center value
    var pivot = arr.splice(pivotIndex, 1)[0];
    console.log(pivot)
    var left = [];　　
    var right = [];
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    //call me loop
    return quickSort(left).concat([pivot], quickSort(right));
};

console.log(quickSort(arr));

这样就报错了。为嘛？

全部回复(5)

ringa_lee2017-04-10 15:56:35 5楼

因为quickSort函数并不是调用一次，而是会不断的调用自己，注意看函数的最后一句。

每次递归调用的时候，数组长度都不同，而递归必须最终能够返回，快速排序才能出结果，否则就会一直递归下去，直到内存耗尽出现栈溢出错误，程序奔溃。

如果对递归不熟悉，可能不太容易理解整个过程。你可以试着运行下面的简单程序，体会一下递归的过程，你的这个快速排序的思想跟这个是类似的（仅就递归而言）。

var calcSum = function(n) {
    if (n == 1) return 1;
    return n + calcSum(n-1);
};
var sum = calcSum(5); // 计算1~5的和

赞 +0

添加回复

迷茫2017-04-10 15:56:35 4楼

报错信息发出来看看

PHPz2017-04-10 15:56:35 3楼

递归调用你没有返回，就会一直不停的调用下去，成了死循环(递归)了

PHP中文网2017-04-10 15:56:35 2楼

这是递归函数啊，没有判断会一直执行，当arr.length=1时不添加判断继续执行的话var pivotIndex = Math.floor(arr.length / 2); pivotIndex=0 然后下次执行该函数是有一个数组长度为0自然就报错了

高洛峰2017-04-10 15:56:35 1楼

确实是这样的，递归结束之后是要有返回的，不然函数永远都结束不掉了！