JavaScript快速排序递归触发Maximum call stack size exceeded错误排查

错误原因 #

你遇到的栈溢出是递归边界设置错误导致的无限递归：
当把基准元素（数组最后一个元素）交换到leftPointer位置后，这个位置的元素已经处于正确的排序位置，不需要再参与左侧子数组的递归排序。但原代码中左侧递归调用仍然传入leftPointer作为右边界：

quickSort(array, leastIndex, leftPointer);

这会导致每次递归都重复处理包含基准元素的子数组，而基准元素所在的子数组永远无法触发if (leastIndex >= highIndex) return;的终止条件，最终引发栈溢出。

修复方案 #

将左侧递归的右边界改为leftPointer - 1，跳过已经排好序的基准元素：

quickSort(array, leastIndex, leftPointer - 1);

修复后的完整代码 #

let array = [1,0,123,1,3,12,2,45,6]
function quickSort(array, leastIndex, highIndex) {
    if (leastIndex >= highIndex) return;

    const pivot = array[highIndex];
    let leftPointer = leastIndex;
    let rightPointer = highIndex;

    while (leftPointer < rightPointer) {
        while (array[leftPointer] <= pivot && leftPointer < rightPointer) {
            leftPointer++;
        }
        while (array[rightPointer] >= pivot && rightPointer > leftPointer) {
            rightPointer--;
        }
        swap(array, leftPointer, rightPointer)
    }
    swap(array, leftPointer, highIndex);
    // 修复左侧递归边界
    quickSort(array, leastIndex, leftPointer - 1);
    quickSort(array, leftPointer + 1, highIndex);
}

function swap(array, a, b) {
    let temp = array[a]
    array[a] = array[b]
    array[b] = temp
}
quickSort(array,0,array.length-1)
console.log(array); // 输出：[0, 1, 1, 2, 3, 6, 12, 45, 123]

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