什么是分区方法（QuickSort算法）中的store变量在做什么？

Question

我在看this简单实现QuickSort算法。

我遇到分区方法的问题。我重新命名变量以帮助我理解。我理解大部分方法，但有一个变量的目的我没有得到。这是store变量。

这是我的这个方法的版本：

private int partition(int[] array, int startIndex, int endIndex) 
{
        int pivotIndex = getPivot(startIndex, endIndex);
        swapElements(array, pivotIndex, endIndex);

        pivotIndex = endIndex;
        int store = startIndex;

        for(int currentIndex = startIndex; (currentIndex <= endIndex - 1); currentIndex++) 
        {
            if(array[currentIndex] <= array[pivotIndex]) 
            {
                swapElements(array, currentIndex, store);
                store++;
            }
        }

        swapElements(array, store, pivotIndex);
        pivotIndex = store;
        return pivotIndex;
}

store变量的目的是什么？如果startIndex和currentIndex已经指向数组的第一个索引，为什么你需要store做同样的事情？它在做什么？

Answer 1

为了回答你更简单的问题，你应该能够看到随着迭代的进行，store与currentIndex不一样。如果array[currentIndex] <= array[pivotIndex]对于特定迭代为真，则仅递增。 - 所以store通常会比currentIndex小。

更具体地说，正在发生的事情是你在开头选择一个指向某个值的pivotIndex。然后，您将在表中移动元素，以便小于pivotIndex值的所有值都在数组中的该值之前，并且所有大于pivotIndex值的值都在数组中的该值之后。 store正在跟踪发现下一个值的位置，该值小于pivotIndex值。该值移动到store位置，然后store递增以移过该值并表示应放置下一个较小值的位置。

在迭代结束时，store的设计指向了枢轴值应该在哪里，因为store之前的所有值都小于该值，并且store之后的所有值都更大。所以最后，数据透视值移动到store指向的位置，store成为分区操作的最终索引，索引指向数据透视值