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

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)

哪些是正确的调用。

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

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

Quicksort - reason for equals checks

java

sorting

algorithm

quicksort