本文详解手写快速排序在处理含重复元素数组时发生栈溢出的根本原因，并提供逻辑严谨、边界安全的分区（partition）实现，重点修正 pivot 定位与双指针扫描逻辑，确保算法在最坏情况下仍能正确收敛。
本文详解手写快速排序在处理含重复元素数组时发生栈溢出的根本原因，并提供逻辑严谨、边界安全的分区（partition）实现，重点修正 pivot 定位与双指针扫描逻辑，确保算法在最坏情况下仍能正确收敛。
快速排序的稳定性与效率高度依赖于 partition 方法的正确性。原代码在处理全相同元素（如 [4, 4, 4, 4]）或大量重复值（如测试用例 [4, 3, 8, 4, 6, 5]）时触发栈溢出，根本原因在于分区逻辑存在两处关键缺陷：
计数范围错误：原代码使用 for(int i = pivotPos+1; i 0（递归深入后），该循环会越界访问无关元素，导致 count 值严重失真，使 pivot 被错误地放置到非法位置，进而造成后续递归区间不收缩（如 si == pivotPos-1 恒成立），最终无限递归。
双指针终止条件与比较逻辑冲突：原 while(i pivotPos) 循环中，对 input[i] pivot 的判断未覆盖等于 pivot 的情况，且未对左右两侧的“等于 pivot”元素做统一归置。这导致相等元素在左右指针间反复交换或滞留，破坏了分区不变式，使 pivotPos 实际分割点失效，递归子区间无法有效缩小。
✅ 正确做法是：
- 严格限定统计范围：仅遍历 [si, ei]，统计严格小于 pivot 的元素个数（而非 ≤），该数值即为 pivot 最终应落位的偏移量（因其左侧应容纳所有更小元素）；
- 精准归置 pivot：将 input[si] 与 input[si + smallerThanPivotCount] 交换，确保 pivot 处于已知正确位置；
- 双指针扫描需覆盖全等场景：左侧指针 i 遇 ≤ pivot 则前进（允许等于 pivot 的元素留在左区），右侧指针 j 遇 ≥ pivot 则后退（允许等于 pivot 的元素留在右区），仅当 i 指向 > pivot 且 j 指向
以下是修复后的完整 partition 方法（已通过 [4,3,8,4,6,5] 等多组含重复数据验证）：
public static int partition(int[] input, int si, int ei) {
int pivot = input[si];
// ✅ 仅统计 [si, ei] 范围内严格小于 pivot 的元素个数
int smallerThanPivotCount = 0;
for (int i = si; i pivot，j 从右找 pivotPos) {
if (input[i] = pivot) {
j--;
} else {
swap(input, i, j);
i++;
j--;
}
}
return pivotPos;
}
// 辅助交换方法（提升可读性）
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
⚠️ 关键注意事项：
- 原 quickSort 递归调用逻辑正确（quickSort(input, si, pivotPos-1) 和 quickSort(input, pivotPos+1, ei)），无需修改，前提是 partition 返回的 pivotPos 真实有效；
- 修复后算法对重复元素具备鲁棒性，时间复杂度在平均情况下仍为 O(n log n)，最坏情况（已排序数组）可通过随机化 pivot 优化；
- 切勿省略 i pivotPos 的循环守卫条件——它保证指针不会越过 pivot 位置，是避免死循环和数组越界的最后防线。
通过聚焦分区逻辑的数学本质（严格小于 pivot 的元素数量决定 pivot 位置），并严格约束操作范围与比较语义，即可彻底规避栈溢出，让手写快排稳健运行于任意输入。
