快速选择分区

Question

我正在努力理解QuickSelect分区是如何工作的，有一些事情我不明白，我会尝试解释我是如何看待它的(请注意，我已经重命名了变量，并发表了我的评论来试图理解它，所以可能一些重命名或评论是错误的(：

• 首先，pivot的值就是pivot所在的索引的值，这是有道理的
• 我们现在将轴心交换到数组的末尾，为什么
• 我们有一个从左边开始的第一个指针，因为第一个指针当然应该从起点开始
• 在for循环中，我们有第二个指针，它也从左边开始，为什么。它不应该从另一端开始吗
• 如果我们所在的位置小于枢轴值，请交换它们，这样我们就可以将较小的元素移到左边
• 在最后交换枢轴回来(这导致我的拳头"为什么"(
• 最后，我们返回第一个指针，我认为这是因为它是数组中唯一剩下的元素

我见过不同类型的实现，我发现大多数(如果不是全部的话(都是这样做的。

// Partitioning.
private static int quickSelectPartition(int[] array, int left, int right, int pivotIndex) {
// The value of the pivot depends on the value at the random index that we got.
int pivotValue = array[pivotIndex];
// Move the pivot to the end.
swapLeftWithRight(array, pivotIndex, right);
// First pointer starts from left.
int firstPointer = left;
// Second pointer starts from left.
for(int secondPointer = left; secondPointer < right; secondPointer++) {
// If the value at the second pointer is less than pivot value, swap it to where the first pointer is.
if(array[secondPointer] < pivotValue) {
//  Swap.
swapLeftWithRight(array, firstPointer, secondPointer);
// Move the first pointer forward.
firstPointer++;
}
}
// When done with this partitioning, swap the pivot back to its original position.
swapLeftWithRight(array, right, firstPointer);
return firstPointer;
}

Answer 1

这一切都与合同有关。quickSelectPartition的契约(如果存在的话(会说类似于"排列数组并返回轴心的新索引；轴心之前的所有元素都小于轴心，轴心之后的所有元素均大于或等于轴心"。

将pivot交换到末尾，然后返回到firstPointer是该函数将其契约连接到循环不变量的方式："索引left..firstPointer-1处的元素小于pivot；索引firstPointer..secondPointer-1处的元素大于或等于pivot"。当secondPointer是left时，这个不变量平凡地成立；循环的目标是将CCD_ 7增加到CCD_。我们可以将枢轴保持在这些数组的中间，但为了回答您的所有问题，不让枢轴不断移动以遵循secondPointer更有效。

当然还有其他方法可以处理分区，所以为什么的元答案是，这是代码作者决定的方法