0

我正在尝试了解 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;
}
4

1 回答 1

0

这都是关于合同的。的合约quickSelectPartition，如果存在的话，会说类似“置换数组并返回枢轴的新索引；枢轴之前的所有元素都小于枢轴，并且枢轴之后的所有元素都大于或等于枢轴”。

将枢轴交换到末尾然后返回firstPointer是该函数如何将其合同连接到循环不变量：“索引处的元素left..firstPointer-1小于枢轴；索引处的元素firstPointer..secondPointer-1大于或等于枢轴”。当secondPointer是时left，这个不变量平凡地成立；循环的目标是在保持不变量secondPointer的同时增加。right我们可以将枢轴保持在这些数组的中间，但要回答您的所有问题，不让枢轴不断移动会更有效secondPointer。

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

于 2018-11-10T19:40:12.313 回答