本文揭示了快速排序实现中常见的递归调用错误：原代码错误地将子问题划分为 [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；随后
仅需递归排序左右两个互不重叠的子区间
。原实现中：
这导致两个致命问题：
区间重叠且未收敛
：[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：
此外，原始 partitioning 方法存在一处潜在风险：rand.nextInt(last - first) + first 在 last == first 时会调用 rand.nextInt(0) 抛出 IllegalArgumentException。虽在 quickSorting 的 if (first < last) 保护下暂不会触发，但仍建议增强鲁棒性（例如在 partitioning 开头添加 if (first >= last) return first;）。
总结
：快速排序的正确性高度依赖分区后子问题的
无重叠性
与
规模严格递减性
。务必确保左右递归调用的边界由 pivotIndex 精确界定，并跳过已确定位置的基准元素——这是避免栈溢出、无限递归及性能骤降的关键。
quickSorting(array, first, last - 1); // ❌ 错误：未排除已定位的 pivot，且左边界未收缩
quickSorting(array, first + 1, last); // ❌ 错误：右区间仍包含 pivot，且与左区间严重重叠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]
}
}