java - 快速选择分区

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

一切都与契约(Contract)有关。 quickSelectPartition 的约定(如果存在)会说类似“置换数组并返回主元的新索引；主元之前的所有元素都小于主元，主元之后的所有元素大于或等于枢轴”。

将枢轴交换到末尾然后返回到 firstPointer 是此函数如何将其契约(Contract)连接到循环不变量:“索引 left..firstPointer-1 处的元素 小于基准；索引 firstPointer..secondPointer-1 处的元素大于或等于基准”。当 secondPointer 为 left 时，此不变量平凡成立；循环的目标是增加 secondPointer 到 right 同时保留不变量。我们可以将枢轴保持在这些数组的中间，但要回答您的所有问题，最好不要让枢轴不断移动以跟随 secondPointer。

当然还有其他方法来处理分区，所以对你的原因的元答案是代码作者决定这样做的方式。