快速排序算法错误

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)];
};

也就是说：

如果左边和右边都有项目，则对两者进行排序
否则，如果左边有项目，则向左排序
否则向右排序

你的逻辑错误如下：你没有处理简单的情况，即 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

但首要的是：您需要首先解决您的 Whosebug 问题，确保您的函数在任何情况下都不会无限次地调用自身，直到浪费足够多的资源导致应用程序崩溃。

快速排序算法错误

quickSort algorithm errore

javascript

sorting

algorithm

quicksort