编程论坛 → C++教室

C++ 归并排序问题？

hcs_xiaohan 发布于 2016-12-14 16:59， 1263 次点击

程序的目的是把两个排序好的向量合并成一个排序的向量。
代码如下：

#include <iostream>
#include <vector>

using namespace std;
void Merge(vector<int> &, int, vector<int> &, int);

int main() {
    vector<int> A, B;
    for(int i = 0; i < 5; i++)
        A.push_back(i * 2 + 1);

    for(int i = 0; i < 7; i++)
        B.push_back(i * 2 +2);

    Merge(A, 5, B, 7);

    for(vector<int>::iterator p = A.begin(); p != A.end(); p++) */
         cout << (*p) << ",";
    cout << endl;

    return 0;
}

void Merge(vector<int> & A, int m, vector<int> & B, int n) {
    vector<int> AA;
    for(int i = 0; i < m; i++)
        AA.push_back(A[i]);

    for(int aa = 0, b = 0, a = 0; aa < m || b < n; ) {
        if(aa < m && (AA[a] <= B[b] || b >= n)) A[a++] = AA[aa++];
        if(b < n && (B[b] <= AA[a] || a >= m)) A[a++] = B[b++];
    }

}

编译报错segmentation default.

请看看是哪儿的问题？

2 回复

#2

rjsp2016-12-15 09:01

根据你源代码修改的

程序代码：

#include <iostream>
#include <vector>
using namespace std;

vector<int> Merge( const vector<int>& a, const vector<int>& b );

int main( void )
{
    vector<int> a, b;
    for( int i=0; i<5; ++i )
        a.push_back( i*2+1 );
    for( int i=0; i<7; ++i )
        b.push_back( i*2+2 );

    vector<int> c = Merge( a, b );

    for( vector<int>::const_iterator itor=c.begin(); itor!=c.end(); ++itor )
        cout << *itor << ',';
    cout << endl;

    return 0;
}

vector<int> Merge( const vector<int>& a, const vector<int>& b )
{
    vector<int> c;
    c.reserve( a.size() + b.size() );

    for( size_t i=0, j=0; i+j!=a.size()+b.size(); )
    {
        if( i<a.size() && (j>=b.size() || a[i]<=b[j]) )
            c.push_back( a[i++] );
        else
            c.push_back( b[j++] );
    }

    return c;
}

#3

rjsp2016-12-15 09:02

再看看用 C++ 怎么做

程序代码：

#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
using namespace std;

int main( void )
{
    vector<int> a = { 1, 3, 5, 7, 9 };
    vector<int> b = { 2, 4, 6, 8, 10, 12, 14 };

    vector<int> c( a.size()+b.size() );
    merge( a.begin(), a.end(), b.begin(), b.end(), c.begin() );

    copy( c.begin(), c.end(), ostream_iterator<int>(cout,",") );
    cout << endl;

    return 0;
}

1