c++ - 合并排序 C++ 编译错误

Question

我正在尝试实现一个合并排序函数，但我收到一个编译器错误，提示“'operator=' 不匹配”它发生在我对 left_list = mergesort(left_list) 的递归赋值中，同样的错误在以下行使用 right_list。

如果我取出赋值并且只有 mergesort(left_list)，它会正确编译，但是它不能正确排序。我认为我现在的方式应该正确合并排序，但鉴于它没有，错误要么与这些行有关，要么在 mergesort() 或 merge() 函数的其他地方。

如有任何帮助，我们将不胜感激。

void mergesort(vector<int> &data) {

vector<int> left_list;
vector<int> right_list;

if ( data.size() <= 1 ) {
    return;
}

// creates a middle point to separate into 2 sub lists
int middle =  ( data.size() / 2 );

// create a list of elements to the left of middle
for ( int i = 0; i < middle; i++ ) {
    left_list.push_back(data[i]);
}

// create a list of elements to the right of middle
for ( unsigned int i = middle; i < data.size(); i++ ) {
    right_list.push_back(data[i]);
}

// break down the sub lists until they are of size 1
left_list = mergesort(left_list);
right_list = mergesort(right_list);

// merge the sublists in the correct order
merge(left_list, right_list);



}

vector<int> merge(vector<int> &left, vector<int> &right) {

vector<int> result;

unsigned left_it = 0;
unsigned right_it = 0;

while( left_it < left.size() && right_it < right.size() ) {


    // the smaller value is put into the result vector
    if( left[left_it] < right[right_it] ) {

        result.push_back(left[left_it]);
        left_it++;
    }
    else
    {
        result.push_back( right[right_it] );
        right_it++;
    }
}

// Put the rest of the data from both vectors onto result
while( left_it < left.size() ) {

    result.push_back( left[left_it] );
    left_it++;
}

while( right_it < right.size() ) {

    result.push_back( right[right_it] );
    right_it++;
}

return result;

}

Answer 1

您的代码试图接受 mergesort 函数的返回值。如果那是你想要的，我的原始答案解决了这个问题。但是，如果 mergesort 应该用排序后的结果更新输入参数，那么它不需要返回任何值，void 就可以了。那么，获取其返回结果的赋值语句是错误的，应该改变。

mergesort(left_list);
mergesort(right_list);

但是，调用merge需要将结果赋值给输入参数。

data = merge(left_list, right_list);

我原来的回答如下:

您应该更改 mergesort 函数以返回与 merge 返回的类型相同的类型。

vector<int> mergesort(vector<int> &data) {

然后您需要更新 mergesort 实现，以便第一个 return 语句返回输入参数:

return data;

应更改最后一条语句以返回结果:

return merge(left_list, right_list);

我没有看过算法本身的实现。