快速排序Hoare数组分区

Question

试图弄清为什么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");?

Answer 1

要执行它，左路至少必须是RightIndex 2，而这是不可能发生的，假设我们从leftIndex＆lt; = rightIndex启动函数：

使用这两个循环：

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个。