时间戳

首页 > 解决方案 > （快速排序算法的）分区方法中的存储变量在做什么？

java - （快速排序算法的）分区方法中的存储变量在做什么？

问题描述

我正在研究快速排序算法的这个简单实现。

我在使用分区方法时遇到问题。我重新命名了变量以帮助我理解。我了解大部分方法，但有一个变量我不明白它的用途。这就是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做同样的事情？它在做什么？

标签： javaquicksort

解决方案

要回答您更简单的问题，您应该能够看到随着迭代的进行store并没有保持不变。只有在特定迭代为真时currentIndex才会增加。array[currentIndex] <= array[pivotIndex]- 所以store通常会小于currentIndex.

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

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

推荐阅读