递归函数单独运行正常但联用栈溢出，求荷兰国旗版快排问题排查

咱们逐个拆解你遇到的两个技术问题：

1. 递归函数单独正常，组合使用触发栈溢出 #

这种情况本质是组合后的递归调用逻辑打破了单个函数的安全边界，常见原因和排查方向如下：

• 递归深度叠加超标：单个函数运行时，处理的数据集小或终止条件触发早，栈深度在JVM默认范围内（通常几百到几千层）；但组合后，比如函数A调用函数B、B又回调A，或者两个函数的递归深度相互叠加，最终超过栈的最大容量。
• 终止条件隐性失效：单独运行时输入刚好符合终止条件，但组合后参数边界计算出现偏差（比如left/right的传递错误），导致递归无法正确终止，进入无限递归直到栈溢出。
• 数据集规模突变：组合后的逻辑可能处理全量数据，比如单个递归只处理小批量数据没问题，但组合后处理大规模有序数组，递归深度达到O(n)级别，直接触发栈溢出。

实用排查建议：

• 在递归函数入口处打印当前递归深度和参数（比如System.out.println("Depth: " + depth + ", left: " + left + ", right: " + right)），观察是否出现深度持续增加或参数异常的情况。
• 逐行检查所有递归调用的终止条件，确保left >= right这类边界判断在任何分支下都能被触发。
• 如果是深度问题，优先考虑将部分递归逻辑改写成迭代（治标又治本），而非临时调整JVM栈大小。

2. 荷兰国旗问题的自定义快速排序变体排查 #

你提供的代码不完整（larger - index ...部分被截断），不过结合荷兰国旗分区的核心逻辑，现有代码大概率存在分区逻辑缺失或递归范围错误，甚至可能和第一个问题的栈溢出直接关联。

现有代码的潜在问题 #

• Pivot选择不合理：直接选nums[left]作为pivot，当数组已经有序时，每次递归只能减少一个元素的处理范围，递归深度达到O(n)，极易触发栈溢出。
• 分区逻辑未实现：荷兰国旗问题需要将数组划分为< pivot、= pivot、> pivot三个区域，但你的代码仅定义了smaller/equal/larger变量却没有实现元素交换逻辑，会导致递归调用范围完全错误。

修正后的完整实现 #

这里给出符合荷兰国旗逻辑的递归排序代码，你可以对照排查：

static void sort(int[] nums) {
    dutchSort(nums, 0, nums.length);
}

// 排序nums[left..right)区间
static void dutchSort(int[] nums, int left, int right) {
    // 递归终止条件：区间长度小于等于1，无需排序
    if (right - left <= 1) return;

    // 优化pivot选择：随机选元素和left交换，避免有序数组的最坏情况
    int pivotIndex = left + (int)(Math.random() * (right - left));
    swap(nums, left, pivotIndex);
    int pivot = nums[left];

    int smaller = left;   // 最后一个小于pivot的元素索引
    int equal = left;     // 最后一个等于pivot的元素索引
    int larger = right;   // 第一个大于pivot的元素索引

    // 遍历分区，直到equal和larger相遇
    while (equal < larger) {
        if (nums[equal] < pivot) {
            // 当前元素小于pivot，交换到smaller区，双指针右移
            swap(nums, smaller, equal);
            smaller++;
            equal++;
        } else if (nums[equal] == pivot) {
            // 当前元素等于pivot，直接右移equal指针
            equal++;
        } else {
            // 当前元素大于pivot，交换到larger区前一位，larger左移
            larger--;
            swap(nums, equal, larger);
        }
    }

    // 递归排序小于/大于pivot的区域，等于区已无需处理
    dutchSort(nums, left, smaller);
    dutchSort(nums, larger, right);
}

// 辅助交换函数
private static void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

关键优化点 #

• 随机Pivot：将平均递归深度降到O(log n)，从根源避免有序数组下的栈溢出问题。
• 严格分区逻辑：明确划分三个区域，递归仅处理未排序的区间，避免无效递归调用。
• 终止条件优化：直接判断right - left <=1，更清晰且避免边界值计算错误。

内容的提问来源于stack exchange，提问作者A is for Ambition