我的 C++ 中的“合并排序”代码有什么问题？

Question

我正在尝试用 C++ 编写合并排序代码，但是存在一些错误，我不知道发生了什么，我没有得到正确的结果

• 5
• 2 1 9 8 7
• 对于上述输入，我没有输出（空白）

//////////////////

• 3
• 2 1 3

此输入结果为 1 3

下面是我的代码

#include <bits/stdc++.h>using namespace std;

void printl(vector<int>&list){
    int n=list.size();
    for(int t=0;t<n;t++){
        cout<<list[t]<<" ";
    }
    cout<<'\n';
}

vector<int> merge(vector<int>&l,vector<int>&r){
    int i,j=0;
    vector<int> m;
    while (i<l.size() && j<r.size()){
        if(l[i]<r[j]){
            m.push_back(l[i]);
            i=i+1;
        }
        else if(r[j]<l[i]){
            m.push_back(r[j]);
            j=j+1;
        }
        else{
            m.push_back(l[i]);
            m.push_back(r[j]);
            i=i+1;
            j=j+1;
        }
    }
    if(i==l.size()) {
        while (j < r.size()) {
            m.push_back(r[j]);
            j = j + 1;
        }
    }
    else if(j==r.size()){
        while(i<l.size()){
            m.push_back(l[i]);
            i=i+1;
    }
    }
    return m;
}

vector<int> merge_sort(vector<int> &list) {
    if (list.size() == 1) {
        return list;
    } else {
        int mid = list.size() / 2;
        auto first = list.begin();
        auto last = list.end();
        vector<int> l(first, first + mid);
        vector<int> r(first + mid, last);
        vector<int> l_ = merge_sort(l);
        vector<int> r_ = merge_sort(r);
        return merge(l_, r_);
    }

}

int main(){
int x;
cin>>x;
    vector<int>inp(x,0);
    for(int v=0;v<x;v++){
        cin>>inp[v];
    }
    vector<int> res=  merge_sort(inp);
    printl(res);

    return 0;
}

堆栈溢出规则很糟糕，我添加了很多细节，请别打扰我。

我正在尝试用 C++ 编写合并排序代码，但是出现一些错误，不知道发生了什么，我没有得到正确的结果 5 2 1 9 8 7 对于上述输入，我没有输出（空白） 3 2 1 3 对于此输入结果是 1 3

Answer 1

我已经审查了您的代码，有几个问题需要解决。主要问题是合并函数中的变量“i”在没有初始化的情况下被使用。此外，还可以进行一些小的改进，以提高代码的可读性。

这是代码的更正版本：

#include <iostream>
#include <vector>

using namespace std;

void printList(const vector<int>& list) {
    for (int t = 0; t < list.size(); t++) {
        cout << list[t] << " ";
    }
    cout << '\n';
}

vector<int> merge(const vector<int>& l, const vector<int>& r) {
    vector<int> m;
    int i = 0, j = 0;

    while (i < l.size() && j < r.size()) {
        if (l[i] < r[j]) {
            m.push_back(l[i]);
            i++;
        } else {
            m.push_back(r[j]);
            j++;
        }
    }

    while (i < l.size()) {
        m.push_back(l[i]);
        i++;
    }

    while (j < r.size()) {
        m.push_back(r[j]);
        j++;
    }

    return m;
}

vector<int> mergeSort(const vector<int>& list) {
    if (list.size() <= 1) {
        return list;
    } else {
        int mid = list.size() / 2;
        vector<int> l(list.begin(), list.begin() + mid);
        vector<int> r(list.begin() + mid, list.end());
        vector<int> l_ = mergeSort(l);
        vector<int> r_ = mergeSort(r);
        return merge(l_, r_);
    }
}

int main() {
    int x;
    cin >> x;

    vector<int> inp(x, 0);

    for (int v = 0; v < x; v++) {
        cin >> inp[v];
    }

    vector<int> res = mergeSort(inp);
    printList(res);

    return 0;
}

主要变化：

在合并函数中初始化“i”以避免未定义的行为。 重命名了函数和变量以遵循更传统的命名风格。 简化合并功能以更有效地处理合并。 在适当的情况下使用 const 作为参数。 请注意，您的 printList 函数是正确的，我已将其保留在更正的代码中。这个更正后的版本应该会为您的合并排序实现产生预期的结果。