javascript - 在Js中使用for循环进行快速排序

Question

我正在编写快速排序算法，当我测试我的代码时，结果让我感到困惑。

RangeError：Array.push () 处超出了最大调用堆栈大小

let arr = [0,-1,1,0,1,-1,100,23,17,56,39,47,23,-34,-56];

export default function quickSort(array){
    let len = array.length;
    if(len <= 1) return array;

    let piviot = array.pop();

    let left = [], right = [];
    for (let i = 0; i < len; i++) {
        if(array[i] < piviot){
            left.push(array[i]);
        }
        else{
            right.push(array[i])
        }
    }
    return quickSort(left).concat(piviot,quickSort(right));
}

当我将 for 循环更改为 forEach 时，问题消失了，但我不知道为什么。

export default function quickSort(array){
    let len = array.length;
    if(len <= 1) return array;

    let piviot = array.pop();

    let left = [], right = [];
    array.forEach(item => {
        if(item < piviot){
            left.push(item)
        }
        else{
            right.push(item);
        }
    });
    return quickSort(left).concat(piviot,quickSort(right));
}

谢谢。

标签： javascriptquicksort

Answer 1

这将在piviot = array.pop();更改导致问题的数组大小时起作用

export default function quickSort(array){
    let len = array.length;
    if(len <= 1) return array;

    let piviot = array.pop();
    len = array.length;
    let left = [], right = [];
    for (let i = 0; i < len; i++) {
        if(array[i] < piviot){
            left.push(array[i]);
        }
        else{
            right.push(array[i])
        }
    }
    return quickSort(left).concat(piviot,quickSort(right));
}