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

Question

我正在研究下面的快速排序实现(来自破解编码面试)。

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

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

否则，使用"左<=右"时，解决方案工作正常。

附言由于"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时left0，right1。这些值将转发到pivot将1partition。由于arr[right] > pivotright将减少，但left保持不变。

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

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

如果您返回left + 1，那么index输入{1, 1}的第一个分区后将是 2，并且您将遇到与quicksort中的第一个分支完全相同的问题。