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

2022-09-04 22:42:29

网络上许多关于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)

有人能为我解决这个难题吗?


答案 1

假设条件已替换为 。i < j

让我们看看对于一个数组会发生什么,比如:

5,4,3,2,1

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

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

然而,如果我们确实有这种情况,循环将终止为 和 现在我们将调用为:i<=ji = 4j = 1

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

这是正确的调用。

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


答案 2