c++ - 快速排序中的堆栈溢出

Question

在开始之前，我只想说我花了大约 2 个小时阅读了关于“快速排序”和“堆栈溢出”的 SO 帖子，所以我不是随便问的，我真的不知道怎么办……

好吧，我必须实现一个快速排序算法，但出于某种原因我找不到，我不断收到堆栈溢出错误。我用的是VS2010，所以我从头到尾都调试过了。

所以，这是我的代码:

const int THRESHOLD = 1;

std::vector<int> data = *new std::vector<int>();

void GetPivotPoint( bool first, int leftBound, int rightBound, int& pivotID )
{
    if( first ) // We are choosing the first element as a pivot
    {
        pivotID = 0;
        return;
    }
    else // We are choosing the median between 1, n/2 and n for our pivot
    {
        int left = leftBound;
        int right = rightBound;
        int center = ( left + right ) / 2;

        if( data[center] - data[left] < 0 ) data_manip::Swap( data, left, center );
        if( data[right] - data[left] < 0 ) data_manip::Swap( data, left, right );
        if( data[right] - data[center] < 0 ) data_manip::Swap( data, center, right );

        data_manip::Swap( data, center, right );
        pivotID = right;
    }
}

int Partition( int left, int right )
{
    int pivotID = 0;
    GetPivotPoint( true, left, right, pivotID );
    int pivot = data[pivotID];

    int i = left - 1;
    int j = right + 1;

    while( i < j )
    {
        i++;
        while( data[i] < pivot ) i++;
        j--;
        while( data[j] > pivot ) j--;

        if( i < j )
        {
            data_manip::Swap( data, i, j );
        }
    }

    return j;
}

void Quicksort( int left, int right )
{
    if( left + THRESHOLD > right )
    {
        algo::Bubblesort( data, left, right );
    }
    else
    {
        int partitionPoint = Partition( left, right );

        Quicksort( left, partitionPoint );
        Quicksort( partitionPoint + 1, right );
    }
} 

下面是 Swap() 方法的实现

inline void Swap( std::vector<int>& data, int p1, int p2 )
    {
        int temp = data[p1];
        data[p1] = data[p2];
        data[p2] = temp;
    }

我使用的是超过 1k 到 500K 的集合。此外，在这个特定的代码中，我使用了将第一个元素作为枢轴的选项，现在我知道这不是最佳的，但我也需要测试该选项。如果我确实使用三的中位数而不是第一个元素，那么我不会得到堆栈溢出，但是，当我使用第一个元素作为枢轴时可能导致它的原因是什么。

感谢帮助

Answer 1

由于以下行，您会出现堆栈溢出。它很微妙但非常重要。您必须将较低的偏移量添加到您计算的中间值。

int center = ( left + right ) / 2;

试试这个:

int center = left + (right - left) / 2;

/////////////////////////////////////////////////////////////////////////////////////

另外，我有一个简单而优雅的实现。它是模板化的，因此它可以处理任何数据类型。该解决方案利用 C++11 移动语义和良好的 API 设计。

如果数组大小可能少于 7 个项目，您可以通过执行插入排序或冒泡排序来优化它，这是一个好主意，因为快速排序本身对于小数组大小来说开销太大

#include <vector>
#include <memory>

template <typename Item>
bool less(Item v, Item w)
{
    // Below line is written assuming that you data implements compareTo method
    // You can also replace it with simple v < w
    return v.compareTo(w) < 0;
}

template <typename Item>
void exch(std::vector<std::shared_ptr<Item>> &arr, int i, int j)
{
    if (i == j) return;

    arr[i].swap(arr[j]);
}

template <typename Item>
class QuickSort
{
public:
    static void sort(std::vector<std::shared_ptr<Item>> &arr)
    {
        sort(arr, 0, arr.size() - 1);
    }

private:
    static void sort(std::vector<std::shared_ptr<Item>> &arr, int lo, int hi)
    {
        if (hi <= lo) return;
        int j = partition(arr, lo, hi);
        sort(arr, lo, j - 1);
        sort(arr, j + 1, hi);
    }

    static int partition(std::vector<std::shared_ptr<Item>> &arr, int lo, int hi)
    {
        int i = lo, j = hi + 1;

        while (true)
        {
            // Find item on left to swap
            while (less((*arr[++i]), (*arr[lo])))
                if (i == hi) break;

            // Find item on right to swap
            while (less((*arr[lo].get()), (*arr[--j].get())))
                if (j == lo) break;

            // Check if pointers swap
            if (i >= j) break;

            // Swap
            exch(arr, i, j);
        }

        // Swap with partitioning item
        exch(arr, lo, j);

        return j;
    }
};