MergeSort中的遞歸

Question

我編輯了我的代碼，刪除了明顯的錯誤。但我仍然無法找到爲什麼我的mergesplit函數不是遞歸的。它只執行一次。請如果有人能給我一個詳細的解決方案。

#include<bits/stdc++.h> 

void Merge_Sort(int a[],int p,int q,int mid); 

void Merge_Split(int a[],int p,int q)//recursive function 
{ 
int mid; 
if (p<q) 
{ 
    mid=(p+q)/2; 
    Merge_Split(a,p,mid); 
    Merge_Split(a,mid+1,q); 
    Merge_Sort(a,p,q,mid); 
} 
return; 
} 

void Merge_Sort(int a[], int p,int q,int mid)//sorting function 
{ 
int b[50]; 
int i,j,x; 
for(i=p,j=mid+1,x=p;i<=mid,j<q;) 
{ 
    if(a[j]<=a[i]) 
    b[x++]=a[j++]; 
    else 
    b[x++]=a[i++]; 
} 
while(i<=mid) 
{ 
    b[x++]=a[i++]; 
} 
while(j<=q) 
{ 
    b[x++]=a[j++]; 
} 
for(int i=p;i<q;i++) 
    a[i]=b[i]; 
} 

int main() 
{ 
int a[5],x=0,n=5; 
for(int i=0;i<n;i++) 
    scanf("%d", &a[i]); 
Merge_Split(a,0,5); 
for(int i=0;i<5;i++) 
    printf("%d", a[i]); 
return 0; 
} 

此代碼應該正常工作。我無法找出我的問題。請幫助。

Answer 1

你搞砸了打開/關閉間隔。一旦您根據您的間隔類型進行了約定，就可以使您的代碼與您的約定保持一致。

Merge_Split(a,0,5)表示您要使用左閉合右開間隔。

在這種情況下：

if (p<q)

Merge_Split(a,p,mid); 
Merge_Split(a,mid,q); 
Merge_Sort(a,p,q,mid); 

和：

for(i=p,j=mid,x=p;i<mid,j<q;)

while(i<mid)

的完整代碼這些變化：

#include<bits/stdc++.h> 

void Merge_Sort(int a[],int p,int q,int mid); 

void Merge_Split(int a[],int p,int q)//recursive function 
{ 
int mid; 
if (p<q - 1) 
{ 
    mid=(p+q)/2; 
    Merge_Split(a,p,mid); 
    Merge_Split(a,mid,q); 
    Merge_Sort(a,p,q,mid); 
} 
return; 
} 

void Merge_Sort(int a[], int p,int q,int mid)//sorting function 
{ 
int b[50]; 
int i,j,x; 
for(i=p,j=mid,x=p;i<mid,j<q;) 
{ 
    if(a[j]<=a[i]) 
    b[x++]=a[j++]; 
    else 
    b[x++]=a[i++]; 
} 
while(i<mid) 
{ 
    b[x++]=a[i++]; 
} 
while(j<q) 
{ 
    b[x++]=a[j++]; 
} 
for(int i=p;i<q;i++) 
    a[i]=b[i]; 
} 

int main() 
{ 
int a[5],x=0,n=5; 
for(int i=0;i<n;i++) 
    scanf("%d", &a[i]); 
Merge_Split(a,0,5); 
for(int i=0;i<5;i++) 
    printf("%d", a[i]); 
return 0; 
}