快速排序递归错误分析与修复方法

本文揭示了快速排序实现中常见的递归调用错误：原代码错误地将子问题划分为 [first, last−1] 和 [first+1, last]，导致无限递归和性能崩溃；正确做法是按基准位置 pivot 划分区间为 [first, pivot−1] 和 [pivot+1, last]。

本文揭示了快速排序实现中常见的递归调用错误：原代码错误地将子问题划分为 `[first, last−1]` 和 `[first+1, last]`，导致无限递归和性能崩溃；正确做法是按基准位置 `pivot` 划分区间为 `[first, pivot−1]` 和 `[pivot+1, last]`。

快速排序的核心在于“分而治之”：每次通过 partitioning 确定一个基准元素（pivot）的最终位置，该位置左侧所有元素 ≤ pivot，右侧所有元素 > pivot；随后仅需递归排序左右两个互不重叠的子区间。原实现中：

quickSorting(array, first, last - 1);  // ❌ 错误：未排除已定位的 pivot，且左边界未收缩
quickSorting(array, first + 1, last);  // ❌ 错误：右区间仍包含 pivot，且与左区间严重重叠

这导致两个致命问题：

• 区间重叠且未收敛：[first, last−1] 和 [first+1, last] 在 last − first ≥ 2 时必然重叠（如 first=0, last=4 → [0,3] 与 [1,4] 重叠于 [1,3]），递归无法有效缩小问题规模；
• 基准未被排除：partitioning 已将 pivot 放置在索引 i+1 处，但后续调用未跳过该位置，造成重复处理甚至死循环（尤其在小数组或重复元素多时）。

✅ 正确的递归分支应严格基于 partitioning 返回的 pivotIndex：

private void quickSorting(int[] array, int first, int last) {
    if (first < last) {
        int pivotIndex = partitioning(array, first, last); // pivotIndex 是 pivot 的最终位置
        quickSorting(array, first, pivotIndex - 1); // 排序左半区：[first, pivotIndex−1]
        quickSorting(array, pivotIndex + 1, last);  // 排序右半区：[pivotIndex+1, last]
    }
}

此外，原始 partitioning 方法存在一处潜在风险：rand.nextInt(last - first) + first 在 last == first 时会调用 rand.nextInt(0) 抛出 IllegalArgumentException。虽在 quickSorting 的 if (first < last) 保护下暂不会触发，但仍建议增强鲁棒性（例如在 partitioning 开头添加 if (first >= last) return first;）。

总结：快速排序的正确性高度依赖分区后子问题的无重叠性与规模严格递减性。务必确保左右递归调用的边界由 pivotIndex 精确界定，并跳过已确定位置的基准元素——这是避免栈溢出、无限递归及性能骤降的关键。