快速选择分区

Question

我试图了解 QuickSelect 分区是如何工作的，有一些事情我没有得到，我将尝试解释我是如何看待它的（请注意，我已重命名变量并发表评论以试图理解它，所以也许一些重命名或评论是错误的）：

• 首先，枢轴的值是枢轴所在索引的值，这是有道理的。

• 我们现在将枢轴交换到数组的末尾，为什么？

• 我们有一个从左边开始的第一个指针，因为第一个指针当然应该从开头开始。

• 在 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，如果存在的话，会说类似“置换数组并返回枢轴的新索引；枢轴之前的所有元素都小于枢轴，并且枢轴之后的所有元素都大于或等于枢轴”。将枢轴交换到末尾然后返回firstPointer是该函数如何将其合同连接到循环不变量：“索引处的元素left..firstPointer-1小于枢轴；索引处的元素firstPointer..secondPointer-1大于或等于枢轴”。当secondPointer是 时left，这个不变量平凡地成立；循环的目标是提高secondPointer到right同时保持不变。我们可以将枢轴保持在这些数组的中间，但要回答您的所有问题，最好不要让枢轴不断移动以跟随secondPointer。当然还有其他处理分区的方法，所以对你的原因的元答案是代码作者决定这样做的方式。