试图找出为什么Hoare分区算法总是将数组分成两个正确的部分在下面的代码中,我扩展了Hoare algorithm以使其更加清晰(有关详细信息,请参见注释)

int partition(int[] arr, int leftIndex, int rightIndex) {
  int pivot = arr[(leftIndex + rightIndex) / 2];

  while (leftIndex <= rightIndex) {
    while (arr[leftIndex] < pivot) leftIndex++;
    while (arr[rightIndex] > pivot) rightIndex--;

    // If all numbers at right places, than leftIndex and rightIndex
    // could point at same array element index
    // So it's means partion done.
    // We should return leftIndex + 1 cause
    // rightIndex points at the last element of the left sub array

    if (leftIndex == rightIndex) return leftIndex + 1;

    if (leftIndex < rightIndex) {
      swap(arr, leftIndex, rightIndex);
      leftIndex++;
      rightIndex--;
    }
  }

  //But here the tricky thing: Why does this "if case" never execute?
  if (leftIndex - 1 > rightIndex)
    System.out.println("leftIndex - 1 > rightIndex");

  return leftIndex;
}

所以问题是:是否可以将一个数组传递给分区函数,这样下面的行就可以执行了?
if (leftIndex - 1 > rightIndex)
  System.out.println("leftIndex - 1 > rightIndex");?

最佳答案

要执行该操作,leftIndex必须至少是rightdindex+2,而且这是不可能发生的,假设我们用leftIndex有了这两个循环:

while (arr[leftIndex] < pivot) leftIndex++;
while (arr[rightIndex] > pivot) rightIndex--;

指数永远不会互相交叉——如果不早一点,它们就会停在枢轴的两边。
如果是这样的话,我们就离开函数:
if (leftIndex == rightIndex) return leftIndex + 1;

所以,唯一剩下的是:
if (leftIndex < rightIndex) {
  swap(arr, leftIndex, rightIndex);
  leftIndex++;
  rightIndex--;
}

即使它们尽可能接近(leftIndex == rightIndex - 1),执行之后它们也将处于leftIndex == rightIndex + 1。我们还是没有得到2分。

07-24 14:43