两路归并排序，

两路归并排序，求助。

C/C++ code

#include <iostream>#include <stdlib.h>#include <vector>#include <fstream>using namespace std;int inversionNum;//typedef vector<int> iArray;vector<int>& mergeSort(vector<int> &i);vector<int>& merge(vector<int> &left, vector<int> &right);int main(){    //read file,initial a integer vector    vector<int> ivec(100000,0);    vector<string> svec(100000);    ifstream fin("beforeSort");    for (vector<string>::iterator sx = svec.begin(); sx != svec.end(); ++sx)        getline(fin, *sx);    fin.close();    //change it into integer    for (int count = 0; count < 100000; ++count)        ivec[count] = atoi(svec[count].c_str());    //merge sort    vector<int> result = mergeSort(ivec);    ofstream fout("afterSort");    for(vector<int>::iterator rx = result.begin(); rx != result.end(); ++rx)        fout << *rx << endl;    fout.close();    cout << "The number of inversions is:" << inversionNum << endl;    return 0;}vector<int>& mergeSort(vector<int>& i) {    if ( i.size() == 1)        return i[0];    vector<int>::iterator mid = i.begin() + i.size() / 2;    vector<int> left.assign(i.begin(), mid);    vector<int> right.assign(mid + 1, i.end());    left = mergeSort( left );    right = mergeSort( right );    return merge( left, right);}vector<int>& merge(vector<int> &left, vector<int> &right) {    vector<int> result;    vector<int>::iterator li = left.begin(), ri = right.begin();    while ( li != left.end() && ri != right.end()) {        if ( left[li] > right[ri] ) {            result.push_back(right[ri]);            ++ri;            ++inversionNum;        }        else {            result.push_back(left[li]);            ++li;            ++inversionNum;        }    }    while ( li != left.end() ) {        result.push_back(left[li]);        ++li;        ++inversionNum;    }    while ( ri != right.end() ) {        result.push_back(right[ri]);        ++ri;        ++inversionNum;    }    return result;}

g++上报了一堆错，最前面的是这样的：

g++ IntegerArray.cc
IntegerArray.cc: In function ‘std::vector<int, std::allocator<int> >& mergeSort(std::vector<int, std::allocator<int> >&)’:
IntegerArray.cc:36: error: invalid initialization of reference of type ‘std::vector<int, std::allocator<int> >&’ from expression of type ‘int’

请各位帮忙看看呐 ：）

[解决办法]
花时间帮你彻底改了一下，修改的地方已标注，未标注的请自己对照着看。编译已通过，你自己运行一下

C/C++ code

#include <iostream>#include <stdlib.h>#include <vector>#include <fstream>using namespace std;int inversionNum;//typedef vector<int> iArray;vector<int> mergeSort(vector<int> &i);                    // 修改1 vector<int> merge(vector<int> &left, vector<int> &right); // 修改2int main(){    //read file,initial a integer vector    vector<int> ivec(100000, 0);    vector<string> svec(100000);    ifstream fin("beforeSort");    for (vector<string>::iterator sx = svec.begin(); sx != svec.end(); ++sx)        getline(fin, *sx);    fin.close();    //change it into integer    for (int count = 0; count < 100000; ++count)        ivec[count] = atoi(svec[count].c_str());    //merge sort    vector<int> result = mergeSort(ivec);    ofstream fout("afterSort");    for(vector<int>::iterator rx = result.begin(); rx != result.end(); ++rx)        fout << *rx << endl;    fout.close();    cout << "The number of inversions is:" << inversionNum << endl;    return 0;}vector<int> mergeSort(vector<int>& i) { // 修改3    if ( i.size() == 1)        return vector<int >(1, i[0]); // 修改4    if ( i.size() == 0){        return vector<int >();    }    vector<int>::iterator mid = i.begin() + i.size() / 2;    vector<int> left(i.begin(), mid);    // 修改5    vector<int> right(mid, i.end());     // 修改6    left = mergeSort( left );    right = mergeSort( right );    return merge( left, right);}vector<int> merge(vector<int> &left, vector<int> &right) { // 修改7：整个函数都有打的改动    vector<int> result;    vector<int>::iterator li = left.begin(), ri = right.begin();    while ( li != left.end() && ri != right.end()) {        if ( *li > *ri ) {            result.push_back(*ri);            ++ri;            ++inversionNum;        }        else {            result.push_back(*li);            ++li;            ++inversionNum;        }    }    while ( li != left.end() ) {        result.push_back(*li);        ++li;        ++inversionNum;    }    while ( ri != right.end() ) {        result.push_back(*ri);        ++ri;        ++inversionNum;    }    return result;} 
  

 

查看更多 下一篇