实现归并排序算法问题

Question

我正在实现一个合并排序算法，并且我在合并算法中接收到一个std::bad_alloc，并且使用CER语句，我发现我的错误在合并算法的第一个循环中。然而，我无法找出哪里出了问题。

vector<int> VectorOps::mergeSort(vector<int> toSort)
{
    if(toSort.size() <= 1)
    {
        return toSort;

    }
    vector<int> left;
    vector<int> right;

    int half = toSort.size()/2;
    for(int i = 0; i < half; ++i)
    {
        left.push_back(toSort.at(i));
    }

    for(int i = half; i < toSort.size(); ++i)
    {
        right.push_back(toSort.at(i));
    }

    //merge algorithim

    vector<int> toReturn;
    while(left.size() > 0 || right.size() > 0)
    {
        cerr << "The numbers are "<< endl;
        if(left.size() > 0 && right.size() > 0)
        {
            if(left.at(0) <= right.at(0))
            {
                toReturn.push_back(left.at(0));
            }
            else
            {
                toReturn.push_back(right.at(0));
            }
        }
        else if(left.size() > 0)
        {
            toReturn.push_back(left.at(0));
        }
        else if(right.size() > 0)
        {
            toReturn.push_back(right.at(0));
        }
    }

    return toReturn;
}

Answer 1

在：

while(left.size() > 0 || right.size() > 0)

left和right的大小永远不会改变(您不会删除head元素)，因此toReturn不受限制地增长，您会耗尽内存。

Answer 2

正如@BenJackson已经在回答中提到的那样...

left和right的大小永远不会改变。您只需从向量中获取元素，而不是将其删除。因此，toReturn的大小无限制地增长。

vector没有任何方法来移除head元素，但您可以实现类似于

left.erase(left.begin());

对于您的解决方案，您可以从向量中删除head元素，或者只迭代向量并获取值。

vector<int> toReturn;
int l = 0; r = 0;
while (l < left.size() || r < right.size()) {

    if (l < left.size() && r < right.size()) {
        if (left.at(l) <= right.at(r)) {
            toReturn.push_back(left.at(l++));
        } else {
            toReturn.push_back(right.at(r++));
        }
    } else if (l < left.size()) {
        toReturn.push_back(left.at(l++));
    } else if (r < right.size()) {
        toReturn.push_back(right.at(r++));
    }
}

通过擦除head元素合并实现。

while (left.size() > 0 || right.size() > 0) {
    cerr << "The numbers are " << endl;
    if (left.size() > 0 && right.size() > 0) {
        if (left.at(0) <= right.at(0)) {
            toReturn.push_back(left.at(0));

            //erase head element from left
            left.erase(left.begin());

        } else {
            toReturn.push_back(right.at(0));

            //erase head element from right
            right.erase(right.begin());

        }
    } else if (left.size() > 0) {
        toReturn.push_back(left.at(0));

        //erase head element from left
        left.erase(left.begin());
    } else if (right.size() > 0) {
        toReturn.push_back(right.at(0));

        //erase head element from right
        right.erase(right.begin());
    }
}