实现合并排序算法问题

Question

我正在实现合并排序算法，我收到合并算法中的std :: bad_alloc并使用cerr语句我发现我的错误是在合并算法的第一个循环中。但是我无法弄清楚什么是错的。

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不会改变大小（你不删除头元素），所以toReturn增长没有约束和你耗尽内存。

Answer 2

由于@BenJackson在回答已经提到...

的left和right的大小不会改变。您只需从矢量中获取元素，而不从中删除。所以，toReturn的大小没有限制地增长。

vector还没有任何方法可以删除头元素，但可以实现像

left.erase(left.begin()); 

您的解决方案无论是从载体中删除头元素或只迭代向量和获得价值。

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++)); 
    } 
} 

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

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()); 
    } 
}