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

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);，导致堆栈溢出错误。

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

示例输入（两个递归函数都被注释掉了），并包括 smaller 的 print 语句：

[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)

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

Recursive functions work fine separately, but together cause stack overflow error

java

stack-overflow

recursion

quicksort