快速选择分区

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。

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