JS；谁能纠正一下我的快速排序函数？

Question

我在使用递归调用时仍然有困难，我的函数超过了最大调用栈。请大家帮忙？

function quickSort(arr) {
    let n = arr[arr.length-1];
    const inf = [];
    const sup = [];
    for(let i = 0; i<arr.length; i++){
        if(arr[i]<= n){inf.push(arr[i])}
        else(sup.push(arr[i]));
    }
    if(inf.length === 1 && sup.length === 1){
        return inf.concat(sup)
    }else if(inf.length === 1 && sup.length > 1){
        quickSort(sup);
        return inf.concat(sup)
    }else if(inf.length > 1 && sup.length === 1){
        quickSort(inf);
        return inf.concat(sup)
    }else{
        quickSort(inf);
        quickSort(sup);
        return inf.concat(sup)
    }
  }

谢谢大家。

Answer 1

让我们举一个数组的例子 arr = [3,2,7,5,4,6].在第一个递归调用中

inf = [3,2,7,5,4,6]
sup = [7]

现在，由于 sup.length === 1 和 inf.length > 1，执行将进入第三个if-else条件。在这个递归调用中，我们有

inf = [3,2,5,4,6] // Same as the original array sent into parameter
sup = []

这基本上属于无限递归调用循环。

为了从这样的无限循环中恢复，你需要添加一个条件来检查当 inf.length === 0 或 sup.length === 0.

可能的解决办法。 在for循环中，在最后一次迭代中，你可以检查任何一个数组是否为空，而且由于最后一次迭代的结果总是相等的情况，即在上面的代码中 arr[i] = n，你可以把它推送到空数组，然后继续执行进一步的if else条件。

考虑到我前面的测试案例，在第二个迭代调用中，我将推送 6 不得 inf[] 但要 sup[] 做出 inf[] 和 sup[] 数组如下。

inf = [3,2,5,4]
sup = [6]

这将解决无限循环的问题。