實現合併排序算法問題

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