合併排序不顯示正確的輸出

Question

我已經實現了合併排序算法明智的每一行，無法找到錯誤。 al和ar是左和右子陣列。數組與大小一起傳遞。

#include<stdio.h> 
#include<conio.h> 
void mergesort(int a[] ,int); 
void merge(int al[],int,int ar[],int,int a[]); 
int main() 
{ 
    int i,n; 
    printf("Enter the no of elements to be sorted\n"); 
    scanf("%d",&n); 
    int a[n]; 
    for(i=0;i<n;i++) 
    { 
     scanf("%d",&a[i]); 
    } 
    mergesort(a,n); 
    printf("\nThe elements after sorting are:"); 
    for(i=0;i<n;i++) 
    { 
     printf("%d ",a[i]); 
    } 
    getch(); 
    return 0; 
} 
void mergesort(int a[],int size) 
{ 
    int i,n=size,mid; 
    if(n<2) 
    return; 
    mid=n/2; 
    int left[mid],right[n-mid]; 
    for(i=0;i<mid;i++) 
    left[i]=a[i]; 
    for(i=mid;i<n;i++) 
    right[i]=a[i]; 
    mergesort(left,mid); 
    mergesort(right,n-mid); 
    merge(left,mid,right,n-mid,a); 
} 
void merge(int al[],int sl,int ar[],int sr,int a[]) 
{ 
    int i=0,j=0,k=0; 
    while(i<sl && j<sr) 
    { 
     if(al[i]<=ar[j]) 
     { 
      a[k]=al[i]; 
      i++; 
     } 
     else 
     { 
     a[k]=ar[j]; 
     j++; 
     } 
     k++; 
    } 
    while(i<sl) 
    { 
      a[k]=al[i]; 
      i++; 
      k++; 
    } 
    while(j<sr) 
    { 
      a[k]=ar[j]; 
      j++; 
      k++; 
    } 
} 

輸入：

no of elements:4 
5 6 3 1 

輸出：

5 16 16 16 

Answer 1

看看你的這部分代碼：

int left[mid],right[n-mid]; 
for(i=0;i<mid;i++) 
left[i]=a[i]; 
for(i=mid;i<n;i++) 
right[i]=a[i]; 

您正在訪問的right陣列超越指數數組邊界。這應該是這樣的，而不是：

right[i - mid]=a[i]; 

Answer 2

我有正確的代碼合併排序用C寫的請與它相符。

#include<stdio.h> 

void mergesort(int a[],int i,int j); 
void merge(int a[],int i1,int j1,int i2,int j2); 

int main() 
{ 
int a[30],n,i; 

      printf("Enter no of elements:"); 
      scanf("%d",&n); 
      printf("Enter array elements:"); 

      for(i=0;i<n;i++) 
      scanf("%d",&a[i]); 
      mergesort(a,0,n-1); 


      printf("\nSorted array is :"); 
      for(i=0;i<n;i++) 
      printf("%d ",a[i]); 
      return 0; 
} 

void mergesort(int a[],int i,int j) 
{ 
      int mid; 
      if(i<j) 
      { 
          mid=(i+j)/2; 
          mergesort(a,i,mid);       
          mergesort(a,mid+1,j);      
          merge(a,i,mid,mid+1,j);     
      } 
} 


void merge(int a[],int i1,int j1,int i2,int j2) 
{ 
      int temp[50];  
      int i,j,k; 
      i=i1;      
      j=i2;      
      k=0; 

      while(i<=j1 && j <=j2)  
      { 
          if(a[i]<a[j]) 
             temp[k++]=a[i++]; 
          else 
             temp[k++]=a[j++]; 
      } 

      while(i<=j1)   
          temp[k++]=a[i++]; 

      while(j<=j2)   
          temp[k++]=a[j++]; 


      for(i=i1,j=0;i<=j2;i++,j++) 
          a[i]=temp[j]; 
}