QuickSort递归触发Maximum call stack size exceeded问题求助

问题重现 #

复制了一段递归实现的快速排序代码，用于排序随机数组时，始终抛出Maximum call stack size exceeded错误。

原代码 #

function quickSort(arr) {
    if (arr.length < 2) { return arr }
    let pivot = arr[arr.length - 1]
    let left = []
    let right = []
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) { left.push(arr[i]) }
        else { right.push(arr[i]) }
    }
    return [...quickSort(left), pivot, ...quickSort(right)]
}

报错信息 #

else { right.push(arr[i]) }
                     ^

RangeError: Maximum call stack size exceeded
    at Array.push (<anonymous>)
    at quickSort (file:///D:/bsc/test.mjs:35:22)
    at quickSort (file:///D:/bsc/test.mjs:37:43)
    at quickSort (file:///D:/bsc/test.mjs:37:43)
    ...
Node.js v17.7.2

问题根源 #

代码的核心逻辑错误在于循环范围包含了基准元素pivot本身：

• 当循环执行到i = arr.length - 1时，arr[i]就是选中的pivot，会被加入right数组
• 递归处理right数组时，又会把这个pivot当作新的基准，再次将其加入新的right数组
• 这个过程无限重复，永远无法触发arr.length < 2的递归终止条件，最终导致调用栈溢出

修复方案 #

修改循环范围，排除基准元素的索引，只遍历数组中除pivot外的其他元素：

修复后的代码 #

function quickSort(arr) {
    if (arr.length < 2) { return arr }
    let pivot = arr[arr.length - 1]
    let left = []
    let right = []
    // 遍历到倒数第二个元素，跳过基准元素
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] < pivot) { left.push(arr[i]) }
        else { right.push(arr[i]) }
    }
    return [...quickSort(left), pivot, ...quickSort(right)]
}

额外优化（可选） #

如果数组中存在大量重复元素，可以将等于pivot的元素单独存放，避免重复递归处理：

function quickSort(arr) {
    if (arr.length < 2) { return arr }
    let pivot = arr[arr.length - 1]
    let left = []
    let mid = []
    let right = []
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i])
        } else if (arr[i] === pivot) {
            mid.push(arr[i])
        } else {
            right.push(arr[i])
        }
    }
    return [...quickSort(left), pivot, ...mid, ...quickSort(right)]
}

内容的提问来源于stack exchange，提问作者deto