標準：在mergesort out_of_range

Question

首先我必須說我是新的算法和c + +。在vim中編寫這段代碼後，當我調試這個C++代碼時，我遇到了error:std:out_of_range，我不知道錯誤在哪裏。所以我在這裏，我非常感謝，如果我得到你的help.thx

#include <iostream> 
#include <cstdio> 
#include <ctime> 
#include <cmath> 
#include <vector> 
#include <iterator> 
#include <algorithm> 
using namespace std; 
void merge(vector<int> &a, int first, int mid, int last) 
{ 
    a.resize(last - first + 1); 
    int n1 = mid - first + 1; 
    int n2 = last - mid; 
    vector<int> larray(n1, 0); 
    vector<int> rarray(n2, 0); 
    for (int i = 0; i != n1; ++i) 
     larray.at(i) = a.at(first + i); 
    for (int i = 0; i != n2; ++i) 
     rarray.at(i) = a.at(mid + 1 + i); 
    int i = 0; 
    int j = 0; 
    int k = 0; 
    while (i < n1 && j < n2) 
    { 
     if (larray.at(k) <= rarray.at(i)) 
      a[k++] = larray[i++]; 
     else 
      a[k++] = rarray[j++]; 
    } 
    while (i < n1) 
     a[k++] = larray[i++]; 
    while (j < n2) 
     a[k++] = rarray[j++]; 
} 

void MegerSort(vector<int> &a, int first, int last) 
{ 
    if (first < last) 
    { 
     int mid = (first + last)/2; 
     MegerSort(a, first, mid); 
     MegerSort(a, mid + 1, last); 
     merge(a, first, mid, last); 
    } 
} 

int main() 
{ 
    vector<int> array; 
    srand(unsigned(time(0))); 
    for (int i = 0; i != 10; ++i) 
     array.push_back(rand() % 10); 
    for (vector<int>::iterator it = array.begin(); it != array.end(); ++it) 
     cout<<*it<<" "; 
    cout<<endl; 
    MegerSort(array, 0, 9); 
    for (vector<int>::iterator it = array.begin(); it != array.end(); ++it) 
     cout<<*it<<" "; 
    return 0; 
} 

Answer 1

我覺得有問題a.resize(last - first + 1);。你不應該這樣做。

假設你叫

void merge(vector<int> &a, int first, int mid, int last)

與first = 6，mid = 7和last = 8。

然後調整後，a有大小=（8 - 6 + 1）= 3

因此，這將是problem-

rarray.at(i) = a.at(mid + 1 + i);你看到mid + 1 = 8