试图找出为什么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分。