关于c++归并排序的问题

Question

c++ 归并排序，下面的代码输出是错的

#include <bits/stdc++.h>
using namespace std;
int a[1005],help[1005];
void mergesort(int L,int R)
{
    if(L>=R)
    {
        return;
    }
    int mid=(L+R)/2;
    mergesort(L,mid);
    mergesort(mid+1,R);
    int l=L,r=mid+1,pos=L;
    while(l<=mid||r<=R)
    {
        if(r>R||(l<=mid&&a[l]<a[r]))
        {
            help[pos++]=a[l++];
        }
        else
        {
            help[pos++]=a[r++];
        }
        for(int i=L;i<=R;i++)
        {
            a[i]=help[i];
        }
    }
}
int main()
{
    int n;
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    mergesort(1,n);
    for(int i=1;i<=n;i++)
    {
        cout<<a[i]<<" ";
    }
    return 0;
}

为什么，可以帮我看一下嘛

Answer 1

该回答引用自GPT-deepseek, 由博主 GISer Liu 编写：

好的，我们来详细分析并解决这个问题。

问题分析

用户提供的C++归并排序代码存在问题，导致输出结果不正确。我们需要仔细检查代码逻辑，找出问题所在，并提供正确的解决方案。

代码审查

1. 归并排序的基本逻辑：归并排序的核心是将数组分成两部分，分别排序，然后合并。用户的代码在合并部分存在逻辑错误。
2. 合并部分的逻辑错误：在合并过程中，用户在每次比较后立即更新原数组a，这是错误的。正确的做法是在整个合并过程结束后再更新原数组。

解决方案

我们需要修改合并部分的逻辑，确保在合并完成后一次性更新原数组。

修改后的代码

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

int a[1005], help[1005];

void mergesort(int L, int R) {
    if (L >= R) {
        return;
    }
    int mid = (L + R) / 2;
    mergesort(L, mid);
    mergesort(mid + 1, R);
    int l = L, r = mid + 1, pos = L;
    while (l <= mid && r <= R) {
        if (a[l] < a[r]) {
            help[pos++] = a[l++];
        } else {
            help[pos++] = a[r++];
        }
    }
    while (l <= mid) {
        help[pos++] = a[l++];
    }
    while (r <= R) {
        help[pos++] = a[r++];
    }
    for (int i = L; i <= R; i++) {
        a[i] = help[i];
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    mergesort(1, n);
    for (int i = 1; i <= n; i++) {
        cout << a[i] << " ";
    }
    return 0;
}

修改说明

1. 合并逻辑修改：

   • 在合并过程中，使用help数组暂存合并结果。
   • 使用两个while循环分别处理左半部分和右半部分的剩余元素。
   • 合并完成后，一次性将help数组中的元素复制回原数组a。

2. 代码结构优化：

   • 移除了不必要的条件判断，简化了代码逻辑。

总结

通过上述修改，确保了归并排序的合并过程正确执行，从而得到正确的排序结果。用户可以直接使用修改后的代码进行测试。

如果该回答解决了您的问题，请采纳！如果没有，请私信联系或评论您的疑惑