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

本文指出并修正了随机主元快排实现中一个关键的递归逻辑错误：原代码错误地对整个子区间重复排序，导致指数级时间复杂度甚至无限递归；正确做法是依据partition返回的主元位置，仅递归处理左右两个不重叠的子区间。

本文指出并修正了随机主元快排实现中一个关键的递归逻辑错误：原代码错误地对整个子区间重复排序，导致指数级时间复杂度甚至无限递归；正确做法是依据partition返回的主元位置，仅递归处理左右两个不重叠的子区间。

该快排实现存在一个致命的递归逻辑缺陷，直接导致算法退化为近乎 O(n²) 甚至陷入死循环或栈溢出——这正是当数组长度超过 30 后响应迟缓、50+ 时“无输出”的根本原因。

问题核心在于 quickSorting 方法中的递归调用：

quickSorting(array, first, last - 1);  // ❌ 错误：未排除已确定位置的 pivot
quickSorting(array, first + 1, last);   // ❌ 错误：区间严重重叠，且未以 pivot 为界

这两行代码完全忽略了 partitioning 的返回值 pivot（即主元在排序后的确切索引），而是机械地缩小区间边界。结果是：

• 左侧递归仍包含 pivot 及其右侧元素；
• 右侧递归仍包含 pivot 及其左侧元素；
• 两个子调用覆盖大量重叠区域，导致同一子数组被反复、冗余地排序；
• 更严重的是，当 first == last - 1 时，first + 1 可能 > last，但因缺少有效终止判断，实际易引发无限递归（尤其在小数组或重复元素多时）。

✅ 正确做法是：利用 partitioning 返回的 pivot 索引，将数组严格划分为三部分：

• [first, pivot−1]：所有 ≤ pivot 的元素（左子区间）
• pivot：主元，位置已最终确定
• [pivot+1, last]：所有 ≥ pivot 的元素（右子区间）

因此，修复后的 quickSorting 方法应为：

private void quickSorting(int[] array, int first, int last) {
    if (first < last) {
        int pivot = partitioning(array, first, last); // 获取主元最终位置
        quickSorting(array, first, pivot - 1);         // ✅ 仅递归左半区
        quickSorting(array, pivot + 1, last);          // ✅ 仅递归右半区
    }
}

此外，还需注意 partitioning 方法中的一处潜在越界风险：
rand.nextInt(last - first) + first 在 first == last 时会调用 rand.nextInt(0)，抛出 IllegalArgumentException。虽然外层 if (first < last) 已规避此情况，但仍建议增强鲁棒性（例如改用 rand.nextInt(last - first + 1) + first 并确保 last >= first）。

总结：快排的效率高度依赖于“分而治之”的正确划分。务必确保每次 partition 后，递归只作用于主元两侧的互斥、无重叠、已明确缩小的子区间。忽视 pivot 的定位意义，是初学者实现快排时最常见也最严重的逻辑错误。