快速排序霍尔数组分区
Quick sort Hoare array partitioning
试图找出为什么霍尔分区算法总是将数组分成两个正确的部分。在下面的代码中,我扩展了 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 必须至少为 rightIndex + 2,而这是不可能发生的,假设我们以 leftIndex <= 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 的差异。
试图找出为什么霍尔分区算法总是将数组分成两个正确的部分。在下面的代码中,我扩展了 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 必须至少为 rightIndex + 2,而这是不可能发生的,假设我们以 leftIndex <= 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 的差异。