JavaScript编写quicksort算法报Maximum call stack size exceeded错误如何解决

报错根本原因 #

• 递归终止条件错误
  原quicksort函数用array.length > 1作为递归执行的判断条件，但所有递归操作都是修改同一个原数组，数组长度全程不会变化，导致判断条件永远成立，递归无法终止，最终触发栈溢出。
• 分区函数quicksortChange逻辑不符合快排区间递归要求
  1. 基准值选取错误：选取基准时用整个数组长度计算位置Math.floor(array.length / 2)，但递归时处理的是[left, right]的子区间，基准应该基于当前子区间的左右边界计算，而非全局数组长度。
  2. 遍历边界错误：遍历的起始位置固定为0、结束位置固定为全局数组末尾，没有使用传入的left和right参数，分区逻辑完全没有对应到当前需要排序的子区间。
  3. 变量未声明：i和j没有用let/const声明，属于隐式全局变量，会导致不同递归层级的变量互相干扰。
  4. 交换逻辑冗余错误：额外增加了a <= b的无效判断，且i、j的自增自减时机错误，容易导致分区返回的边界值异常，进一步造成递归无法收敛。

修正后完整代码 #

function quicksort(array, left, right) {
    // 修正终止条件：子区间长度小于等于1时直接返回
    if (left >= right) return array
    let sort = quicksortChange(array, left, right)
    // 递归排序左半区间
    quicksort(array, left, sort - 1)
    // 递归排序右半区间
    quicksort(array, sort, right)
    return array
}

// 修正后的分区函数
function quicksortChange(array, left, right) {
    // 取当前子区间的中间位置作为基准
    let pivot_number = Math.floor((left + right) / 2)
    let pivot = array[pivot_number]
    let i = left
    let j = right
    while (i <= j) {
        // 左指针向右找第一个大于等于基准的值
        while (array[i] < pivot) {
            i++
        }
        // 右指针向左找第一个小于等于基准的值
        while (array[j] > pivot) {
            j--
        }
        if (i <= j) {
            // 交换两个值
            [array[i], array[j]] = [array[j], array[i]]
            i++
            j--
        }
    }
    // 返回分区边界
    return i
}

调用代码不需要修改：

// 调用示例
const array = [3,6,2,7,1,9,4,8,5]
let cleanArray = quicksort(array, 0, array.length - 1)
console.log(cleanArray)

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