Java实现3-Way Quicksort遇StackOverflowError栈溢出求助

1. 基本类型值传递导致划分边界完全失效 #

Java 对基本类型参数采用值传递规则，在 quickSortByRecursion 中定义的局部变量 i、j，调用 partition 时仅将初始值 0 拷贝给方法形参。partition 内部对 i、j 的所有修改，仅作用于自身栈帧的局部副本，不会影响外部 quickSortByRecursion 中的变量值。
最终递归调用的两个分支实际传参为固定值：

• 左分支：quickSortByRecursion(intArray, low, 0)
• 右分支：quickSortByRecursion(intArray, 0, high)

以初始调用为例：排序入口传入的参数为 low=0, high=9，调用完 partition 后 i/j 仍为初始值0，此时右递归分支等价于调用 quickSortByRecursion(arr, 0, 9) —— 重复执行参数完全一致的递归调用，最终撑爆栈空间触发 StackOverflowError。

2. partition 方法控制流逻辑反向，划分功能完全失效 #

现有 partition 的分支判断存在结构错误：

if(high - low <= 1) {
    // 仅处理长度≤2的小区间交换逻辑
} else {
    i = low;
    j = high;
    return; // 只要区间长度>2，直接走该分支返回
}
// 以下3路划分的核心while循环，仅当区间长度≤2时才可被执行

只要待排序区间长度超过2，partition 直接进入 else 分支返回，后续的3路划分核心逻辑永远不会被执行，完全丧失数组划分的作用。

3. 3路划分核心逻辑存在多处索引错误 #

即便修正控制流和传参问题，现有 while 循环内的逻辑也无法正确完成3路划分：

• 选取 pivot 为区间最右端元素后，未对 pivot 做位置前置处理，遍历边界与 pivot 位置错位
• 元素比较后的交换索引不符合3路划分规则：遇到小于 pivot 的元素时，错误交换 low+1 与 midpoint+1 位置，未维护「小于pivot区、等于pivot区、大于pivot区」的三段连续边界
• 循环内部反复将 i 赋值为 low-1、j 赋值为 midpoint，这两个值并非划分完成后的合法子区间边界

• 解决值传递无法回传划分边界的问题：修改 partition 方法，直接返回长度为2的 int 数组，分别存储小于 pivot 区域的右边界、大于 pivot 区域的左边界，替代原来靠形参回传值的方式。
• 修正 partition 的控制流结构：删除原有的 high-low <=1 分支嵌套，对任意长度的待排序区间都执行划分逻辑，仅在递归出口对长度≤1的区间直接返回。
• 对齐标准3路划分逻辑：采用 lt（小于区右边界）、gt（大于区左边界）、midpoint（当前遍历指针）三个变量维护划分状态，遍历规则为：
  1. 初始状态：lt = low, midpoint = low, gt = high
  2. 当前元素 < pivot：交换 lt 与 midpoint 位置元素，lt、midpoint 分别右移一位
  3. 当前元素 == pivot：midpoint 右移一位
  4. 当前元素 > pivot：交换 midpoint 与 gt 位置元素，gt 左移一位
• 修正递归调用的传参：拿到 partition 返回的正确边界后，仅递归排序 [low, lt-1]（小于pivot的区域）和 [gt+1, high]（大于pivot的区域），跳过已排序的等于pivot的中间段，保证每次递归处理的区间范围严格缩小，避免无限递归。

内容的提问来源于stack exchange，提问作者stafino