quickSort算法错误

Question

let quickSort = (arr) => {
    let pivot = arr[arr.length - 1];
    const rightArr = [];
    const leftArr = [];
    for(let i = 0; i < arr.length - 1 ; i++){
        if (arr[i] > pivot){
            rightArr.push(arr[i]);
        }else{
            leftArr.push(arr[i]);
        };
    };
    if (leftArr.length > 0 && rightArr.length > 0 ){
        return [...quickSort(leftArr) , pivot , ...quickSort(rightArr)];
    }else if (leftArr.length > 0){
        return [...quickSort(leftArr) , pivot]; 
        
    }else {
        return [pivot ,...quickSort(rightArr)];
    };
};
quickSort(arr);

为什么最大调用堆栈大小超过了(递归函数仍然存在问题)

Answer 1

在quickSort内部，您有以下代码：

if (leftArr.length > 0 && rightArr.length > 0 ){
    return [...quickSort(leftArr) , pivot , ...quickSort(rightArr)];
}else if (leftArr.length > 0){
    return [...quickSort(leftArr) , pivot]; 
    
}else {
    return [pivot ,...quickSort(rightArr)];
};

上面写着：

如果在左边和右边都有项目，则对both

• otherwise，进行排序，如果在左边有项，则排序到左

• ，否则将排序到右

。

您的逻辑错误如下：--您不处理琐碎的情况，也就是说，leftArr和rightArr的长度都不大于0。您也需要处理这个问题，

下面的代码修复了一个错误。我并不认为您的代码将在之后正确工作，但是下面的代码解决了上面描述的逻辑问题：

//calculate pivot

if (leftArr.length > 0 && rightArr.length > 0 ){
    return [...quickSort(leftArr) , pivot , ...quickSort(rightArr)];
}else if (leftArr.length > 0){
    return [...quickSort(leftArr) , pivot]; 
}else if (rightArr.length > 0){
    return [pivot ,...quickSort(rightArr)];
}else {
    return pivot;
};

我在评论中说，你需要计算枢轴。有多种可能的方法可以这样做，请参阅https://javascript.plainenglish.io/quick-sort-algorithm-in-javascript-5cf5ab7d251b

但是第一件事是:首先需要修复堆栈溢出问题，确保在任何情况下函数都不会无限多次地调用自己，直到浪费足够的资源才能使应用程序崩溃。