Quicksort - 等于检查的原因

Question

关于Quicksort(Java)的网络上的许多例子都接近于此:

private void quicksort(int low, int high) {
    int i = low, j = high;
    int pivot = numbers[low + (high-low)/2];

    while (i <= j) {

      while (numbers[i] < pivot) {
        i++;
      }

      while (numbers[j] > pivot) {
        j--;
      }

      if (i <= j) {
        exchange(i, j);
        i++;
        j--;
      }
    }

    if (low < j)
      quicksort(low, j);
    if (i < high)
      quicksort(i, high);
}

我很困惑的是为什么有那些平等的检查:

1)while (i <= j)而不是while (i < j)

2)if (i <= j)而不是if (i < j)

是否有任何边缘情况,这等于是至关重要的？根据我的理解,如果我们有if(i == j),那么我们基本上会用相同的值交换相同的值.

有人可以帮我解决这个难题吗？

Answer 1

假设条件被替换为i < j.

让我们看看数组会发生什么:

5,4,3,2,1

while循环将以i = 2和终止j = 2,并且我们将重叠调用函数quicksort,这些调用将是:

quicksort(0,2) and quicksort(2,4)

而如果我们确实有这个条件i<=j的循环将与终止i = 4和j = 1现在我们将不得不调用为:

quicksort(0,1) and quicksort(3,4)

这是正确的电话.

所以基本上你是对的,交换相同的元素是没有意义的,但代码的作者必须省略它,以避免在我等于j时添加一个你不需要交换的额外条件