java - 递归函数单独工作正常，但一起导致堆栈溢出错误

Question

在处理 Dutch National Flag Problem 时，我想出了下面的代码，希望能实现我自己的快速排序变体:

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

// sorts nums[left..right)
static void dutchSort(int[] nums, int left, int right) {
    // recursion base case
    if (left >= right) return;

    int pivot = nums[left];

    // smaller - index of the last element smaller than pivot value
    // equal - index of the last element equal to pivot value
    // larger - index of the first element larger than pivot value
    int smaller = left-1, equal = left, larger = right, temp;

    // before sorting is completed, 'equal' is the current index,
    // much like 'i' in a for-loop
    while (equal < larger) {
        if (nums[equal] < pivot) {
            temp = nums[equal];
            nums[equal] = nums[++smaller];
            nums[smaller] = temp;
        } else if (nums[equal] == pivot) {
            equal++;
        } else {
            temp = nums[equal];
            nums[equal] = nums[--larger];
            nums[larger] = temp;
        }
    }

    // recursively sort smaller subarray
    dutchSort(nums, 0, smaller+1);

    // recursively sort larger subarray
    dutchSort(nums, equal, nums.length);
}

生成的排序数组理想情况下应由 3 个子数组组成:(i) 所有小于主元的值，(ii) 所有等于主元的值，(iii) 所有大于主元的值。然后对子数组 (i) 和 (iii) 进行递归排序，直到对大小为 1 的子数组的基本情况进行排序。我认为我的代码正确地做到了这一点，但我不是 100% 确定。 while 循环中的逻辑，以及递归调用中用于left 和right 的值也是正确的。

但是dutchSort函数最后的两次递归调用，dutchSort(nums, 0, smaller+1);和dutchSort(nums, equal, nums.length);，导致栈溢出错误。

当我注释掉两个递归函数或其中一个递归函数时，程序终止并生成一个正确排序(或部分排序)的数组。

示例输入(注释掉了两个递归函数)，并包含一个print语句用于smaller:

[2,0,1,0,0,2]

输出:

smaller = 3
[0, 1, 0, 0, 2, 2]

虽然实际上没有排序，但这仍然是一个正确的输出，因为枢轴左侧的所有值都是较小的值。然后理想情况下，这两个递归函数将处理适当的子数组。在这种情况下，只有较小的子数组 [0,1,0,0] 需要排序。请注意，smaller = 3 正确显示索引 [0..3] 中的子数组需要排序。

使用输入 [0,1,0,0] 重新启动程序，再次注释掉递归函数，我正确地得到:

[0,0,0,1]

看来排序逻辑是正确的；原始数组排序正确，手动排序适当的子数组也可以。但是，当所有内容都取消注释并合并时，就会出现导致堆栈溢出的循环。

请帮我找出造成这种行为的原因。

谢谢:)

Answer 1

我认为你的第一个递归调用应该使用 left 作为第二个参数:

dutchSort(nums, left, smaller+1)

代替

dutchSort(nums, 0, smaller+1)