本文解析 javascript 中快速排序（quicksort）实现时因未跳过基准元素导致的无限递归问题，并提供修正代码与调试建议。
本文解析 javascript 中快速排序（quicksort）实现时因未跳过基准元素导致的无限递归问题，并提供修正代码与调试建议。
快速排序是一种经典的分治（Divide and Conquer）排序算法，其核心思想是：选取一个基准值（pivot），将数组划分为“小于基准”和“大于等于基准”的两部分，再递归地对这两部分排序。然而，一个看似微小的索引错误——在分区循环中未跳过 pivot 元素本身——会导致逻辑错误，进而引发无限递归。
在原始代码中，for (let i = 0; i = pivot 恒成立），导致 highterThanPivot 始终包含至少一个元素（即 pivot 本身）。当该子数组传入下一层递归时，它仍满足 arr.length >= 2（例如 [5] 变成 [5, 5] 后不断膨胀），且 pivot 持续被重复纳入，最终使子问题规模不缩减，触发栈溢出或无限循环。
✅ 正确做法是：从索引 1 开始遍历，跳过已选为 pivot 的首元素：
const quickSort = function (arr) {
if (arr.length < 2) {
return arr; // 基础情况：空数组或单元素数组直接返回
}
const pivot = arr[0];
const smallerThanPivot = [];
const higherThanPivot = []; // 修正拼写：'highter' → 'higher'
for (let i = 1; i < arr.length; i++) { // ? 关键修复：i 从 1 开始
if (arr[i] < pivot) {
smallerThanPivot.push(arr[i]);
} else {
higherThanPivot.push(arr[i]);
}
}
return [
...quickSort(smallerThanPivot),
pivot,
...quickSort(higherThanPivot)
];
};
// 测试示例
console.log(quickSort([3, 6, 8, 10, 1, 2, 1]));
// 输出: [1, 1, 2, 3, 6, 8, 10]⚠️ 注意事项：
- 避免重复包含 pivot：除跳过索引 0 外，也可改用 filter() 配合 slice(1) 显式排除 pivot，提升可读性；
- 稳定性与重复元素处理：当前实现将等于 pivot 的元素全部归入 higherThanPivot，适用于通用排序；若需稳定划分（如分离 ），可额外维护 equalThanPivot 数组；
- 性能提醒：此实现空间复杂度为 O(n)，且最坏情况（如已排序数组选首元素为 pivot）时间复杂度退化为 O(n²)；生产环境推荐使用内置 Array.prototype.sort() 或优化版三数取中 pivot 策略；
- 调试技巧：如遇类似递归问题，可在关键位置添加 console.log({ pivot, smallerThanPivot, higherThanPivot }) 快速验证子数组是否按预期收缩。
掌握这一细节，不仅能修复无限循环，更能加深对分治算法“子问题独立性”和“规模严格递减”原则的理解。
