java - 快速选择分区

我试图了解QuickSelect分区是如何工作的，还有一些事情我不知道，我将尝试解释我是如何看待它的（请注意，我已经重命名了变量并发表了我的评论以试图理解它，所以可能有些重命名或评论是错的）：
首先，pivot的值是pivot所在索引的值，这是有意义的。
我们现在将轴交换到数组的末尾，为什么？
我们有一个从左边开始的第一个指针，因为第一个指针当然应该从开头开始。
在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;
}

最佳答案

都是关于合同的如果将轴交换到末尾，然后再交换回quickSelectPartition是此函数将其契约连接到循环不变量的方式：“索引firstPointer处的元素小于轴；索引left..firstPointer-1处的元素大于或等于轴”。当firstPointer..secondPointer-1是secondPointer时，这个不变量一般成立；循环的目标是在保持不变量的同时将left增加到secondPointer。我们可以将轴心保持在这些数组的中间，但是要回答您的所有问题，不让轴心不断移动来跟随right会更有效率。
当然还有其他处理分区的方法，所以你的理由的元答案是，这是代码作者决定的方法。