java - 快速排序 - 相等检查的原因

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)

是否存在任何边缘情况，其中 equals 是至关重要的？根据我的理解，如果我们有 if(i == j) ，那么我们基本上会用相同的值交换相同的值。

谁能帮我解开这个谜题？

Answer 1

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

让我们看看像这样的数组会发生什么:

5,4,3,2,1

while 循环将终止于 i = 2和 j = 2 ，并且我们将对快速排序函数进行重叠调用，这些调用将是:

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

而如果我们确实有这个条件 i<=j循环将以 i = 4 终止和 j = 1现在我们会这样调用:

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

哪些是正确的调用。

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