将此 Quicksort 实现的比较器从 <= 更改为 < 会导致无限递归。为什么？

Question

我正在研究下面的 Quicksort 实现（来自 Cracking the Coding Interview）。

在分区方法中，有两个 "left <= right" 谓词（在其第一个 while 语句和最后一个 if 语句中）。当 left == right 时，交换这些索引处的元素与不交换相同，所以我认为删除比较的“==”部分不会有任何影响。但是，当我这样做并且运行代码而不是 "left < right" 时，程序无限递归（在某些输入上）并导致堆栈溢出。为什么？

澄清：我正在将分区方法中的 "left <= right" 谓词更新为 "left < right"，在 (1) 第一个 while 语句和 (2) 最后的 if 语句中。

否则，该解决方案在使用 "left <= right" 时工作正常。

P.S。由于 "left" 在最后一个 if 语句中递增，我也尝试返回 left+1，但这仍然会导致无限递归。

public static void quickSort(int[] arr, int left, int right) {
    int index = partition(arr, left, right);
    if (left < index - 1) { // Sort left half
        quickSort(arr, left, index - 1);
    }
    if (index < right) { // Sort right half
        quickSort(arr, index, right);
    }
}

public static int partition(int[] arr, int left, int right) {
    int pivot = arr[(left + right) / 2]; // Pick a pivot point. Can be an element        
    while (left <= right) {
        // Find element on left that should be on right
        while (arr[left] < pivot) { 
            left++;
        }

        // Find element on right that should be on left
        while (arr[right] > pivot) {
            right--;
        }

        // Swap elements, and move left and right indices
        if (left <= right) {
            swap(arr, left, right);
            left++;
            right--;
        }
    }
    return left; 
}

public static void swap(int[] array, int i, int j) {
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}

Answer 1

让我们举一个简单的例子，其中要排序的数组是{1, 2}。第一次调用quicksort时，left为0，right为1。这些值将被转发到 partition，其中 pivot 将是 1。由于 arr[right] > pivot right 将递减，但 left 保持不变。

由于分区 left < right 中的 while 循环结束时为假，因此不会交换任何内容并且循环将退出，因为它具有相同的条件。 partition 将 return left 为 0 并分配给 index.

下一个 quicksort 将跳过第一个分支，因为 left < index - 1 为假。第二个分支将从index < right开始执行，quicksort被称为index和right，其值分别为0和1。现在，如果我们从头开始，我们会看到 quicksort 最初是用完全相同的值调用的，这解释了无限递归。

如果你 return left + 1 而不是 index 将在输入 {1, 1} 的第一个分区后为 2 并且你将与 [= 中的第一个分支完全相同的问题11=]。

将此 Quicksort 实现的比较器从 <= 更改为 < 会导致无限递归。为什么？

Changing this Quicksort implementation's comparator from <= to < causes infinite recursion. Why?

java

sorting

algorithm

recursion

quicksort