快速选择分区

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。

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