关于#算法#的问题：这个算法我是根据教学PPT上的伪代码翻译的，检查了一下午也没找到问题在哪(语言-c++)

Question

这个算法我是根据教学PPT上的伪代码翻译的，检查了一下午也没找到问题在哪，求指点。（附上伪代码

）

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


void Merge(int A[],int p,int q,int r){
    int x=q-p+1,y=r-q;
    int B[x],C[y];
    int k=0;
    for(int i=p;i<=q;i++){
        B[k++]=A[i];
    }
    k=0;
    for(int i=q+1;i<=r;i++){
        C[k++]=A[i];
    }    
    int i,j=0;
    k=p;
    while(i<x && j<y){
        if(B[i]<=C[j]){
            A[k]=B[i];
            i++;        
        }
        else {
            A[k]=C[j];
            j++;
        }
        k++;
        
    }
    if(i>=x){
        for(int m=j;m<y;m++){
            A[k]=C[m];
            k++;
        }
    } 
    else{
        for(int n=i;n<x;n++){
            A[k]=B[n];
            k++;
        }
    }
}

void MergeSort(int A[],int p,int r){
    if(p<r){
        int q=(p+r)/2;
        MergeSort(A,p,q);
        MergeSort(A,q+1,r);
        Merge(A,p,q,r);
    }
}
int main(){
    int s;
    cin>>s;
    int S[s];
    for(int i=0;i<s;i++){
        cin>>S[i];
    }
    MergeSort(S,0,s-1);
    for(int i=0;i<s;i++){
        cout<<S[i]<<" "; 
    }
    return 0;
} 

Answer 1

#include<iostream>
using namespace std;
//合并排序
int Mergesort(int a[],int left,int right);
void Merge(int a[],int left,int mid,int right);
  
int main()
{
    int n;
    cin>>n;
    int *a=new int[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }

    Mergesort(a,0,n-1);

    for(int i=0;i<n;i++)
    {
        cout<<a[i]<<" ";
    }
    delete [] a;
    return 0;
}

int Mergesort(int *a,int left,int right)
{
    if(left<right)
    {
        int mid=(left+right)/2;
        Mergesort(a,left,mid);
        Mergesort(a,mid+1,right);
        Merge(a,left,mid,right);
    }
    else{return 0;}
}

void Merge(int *a,int left,int mid,int right)
{
    int *b=new int[right-left+1];
    int i=left,j=mid+1;
    int k=0;
    while(i<=mid&&j<=right)
    {
        if(a[i]>a[j])
        {
            b[k]=a[j];
            k++;
            j++;
        }
        else
        {
            b[k]=a[i];
            k++;
            i++;
        }

    }
    while(i<=mid)
    {
        b[k++]=a[i++];
    }
    while(j<=right)
    {
        b[k++]=a[j++];
    }
    int site=0; 
    for(int m=left;m<=right;m++)
    {
        a[m]=b[site++];
    }
    delete [] b;
}

具体看 https://blog.csdn.net/YTLDSS/article/details/123962059