快速 select 分区

Question

我试图了解 QuickSelect 分区的工作原理，但有几件事我不明白，我将尝试解释我的看法（请注意我已重命名变量并发表评论试着理解它，所以也许有些重命名或评论是错误的）：

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

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

// 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 的合同，如果存在的话，会说类似 "permutes the array and returns the new index of the pivot; all elements before the pivot are less than the pivot, and all elements after the pivot are greater than or equal to the pivot".

的内容

将枢轴交换到末尾然后返回到 firstPointer 是此函数将其合同连接到循环不变量的方式："the elements at indexes left..firstPointer-1 are less than the pivot; the elements at indexes firstPointer..secondPointer-1 are greater than or equal to the pivot"。当 secondPointer 为 left 时，此不变量平凡成立；循环的目标是将 secondPointer 增加到 right，同时保留不变量。我们可以将枢轴保持在这些数组的中间，但要回答您的所有问题，最好不要让枢轴不断移动以跟随 secondPointer.

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

快速 select 分区

Quick select partitioning

java

algorithm

big-o

quicksort

quickselect