我初始化为0的变量随机变成了-1？

Question

我正在尝试实现基于向量的快速排序。但是我运行遇到了运行ge 异常，我无法弄清楚我的代码有什么问题。

void myQuicksort(std::vector<int>& values, int first, int last);

int largest(std::vector<int>& values)
{
    //using Quicksort
    int first = 0;
    int last = values.size() - 1;
    myQuicksort(values, first, last);
    return values[last-1];
    
}

void myQuicksort(std::vector<int>& values, int first, int last)
{
    int cnt1, cnt2, pivot, Temporary;
    if (first < last)
    {
        pivot = first;
        cnt1 = first;
        cnt2 = last;
        while (cnt1 < cnt2)
        {
            while (values[cnt1] <= values[pivot] && (cnt1 < last))
            {
                cnt1++;
            }
            while (values[cnt2] > values[pivot])
            {
                cnt2--;
            }
            if (cnt1 < cnt2)
            {
                Temporary = values[pivot];
            }
        }
        Temporary = values[pivot];
        values[pivot] = values[cnt2];
        values[cnt2] = Temporary;
        myQuicksort(values, first, cnt2 - 1);
        myQuicksort(values, cnt2 - 1, last);
    }
}

int main()
{
    std::vector<int> signature = { 0,21,34,55,8,13,1,1,2,3,5 };
    std::cout << largest(signature)<<std::endl; 
}

我使用调试器发现“第一个”变量被重新分配为 -1。没有关于为什么会发生这种情况的线索。这导致运行ge 异常。

Answer 1

正如 Thomas Sablik 和 Andreas Wenzel 所指出的，主要问题出在对 myQuickSort() 的第二次调用中，应该是

std::swap(values[pivot], values[cnt2]);
myQuicksort(values, first, cnt2 - 1);
myQuicksort(values, cnt2 + 1, last);   // <-- passing cnt2 - 1 here discarded the pivot

因为你刚刚交换了 values[cnt2] 和 values[pivot]，所以把这次迭代的中心放在正确的地方，即 cnt2.
因此，下一次迭代必须避免 cnt2 和运行在它之前和之后

这两个比较都必须小于等于而不是刚好小于

// If only this comparison is <= the loop doesn't end
while (cnt1 <= cnt2)
{
    // If only this comparison is <= it doesn't sort correctly
    while (values[cnt1] <= values[pivot] && (cnt1 <= last))

Andreas Wenzel 还指出，在 if (cnt1 < cnt2) 下的代码块中，代码实际上并未执行任何操作。在我看来，您似乎开始编写交换，只是忘记完成它:)
不管怎样，这是一个固定版本。

void myQuicksort(std::vector<int>& values, int first, int last)
{
    if (first >= last)
        return;

    int cnt1 = first;
    int cnt2 = last;
    int pivot = first;

    while (cnt1 <= cnt2)
    {
        while (values[cnt1] <= values[pivot] && (cnt1 <= cnt2)) // It just needs to go to cnt2, not last
            cnt1++;

        while (values[cnt2] > values[pivot])
            cnt2--;

        if (cnt1 < cnt2)
        {
        // Temporary = values[pivot]; had no effect
        // It is very likely that an IDE would have shown a warning due to static code analysis
            std::swap(values[cnt1], values[cnt2]);
            cnt1++;
            cnt2--;
        }
    }
    std::swap(values[pivot], values[cnt2]);
    myQuicksort(values, first, cnt2 - 1);
    myQuicksort(values, cnt2 + 1, last);  // <-- passing cnt2 - 1 here discarded the pivot
}

就像其他人已经建议的那样，调试器对于开发算法非常有用，因为您可以逐步检查代码并检查变量。
此外，使用带有静态分析器的 IDE 可以帮助您在输入错误后立即识别它们。

我初始化为0的变量随机变成了-1？

The variable I initialised as 0 randomly turns into a -1?

c++

sorting

vector

quicksort

stdvector