Mergesort在執行時爲排序數組的第一個元素提供垃圾值

Question

我對編程不熟悉，現在已經編程了幾個星期。我使用「算法簡介」中描述的算法實施Mergesort。但是，每次執行時，我都會得到一個垃圾值作爲排序數組的第一個元素。請幫助確定問題。下面是它的代碼：

#include <stdio.h> 
#include <stdlib.h> 
#include <limits.h> 

void mergesort(int a[], int p, int r); 

void merge(int a[], int p, int q, int r) 
{ 
    int *left, *right; 
    int i,j,k,l,n1,n2; 
    n1 = q-p+1; 
    n2 = r-q; 
    left = malloc(sizeof(int)*(n1+1)); 
    right = malloc(sizeof(int)*(n2+1)); 
    for (i = 0; i < n1; i++) { 
     left[i] = a[p+i]; 
    } 
    for (j = 0; j < n2; j++) { 
     right[j] = a[q+j+1]; 
    } 
    left[n1] = INT_MAX; 
    right[n2] = INT_MAX; 
    i = 0; 
    j = 0; 
    for (k = p; k <= r; k++) { 
     if (left[i] <= right[j]) { 
      a[k] = left[i]; 
      i++; 
     } 
     else { 
      a[k] = right[j]; 
      j++; 
     } 
    } 
    free(left); 
    free(right); 
    return ; 
} 

int main(int argc, char* argv[]) 
{ 
    int i; 
    int a[] = {5,2,4,7,1,3,2,6} ; 
    mergesort(a,0,sizeof(a)/sizeof(int)); 
    for (i = 0; i < sizeof(a)/sizeof(int); i++) { 
     printf("%d\n",a[i]); 
    } 
    return 0; 
} 

void mergesort(int a[], int p, int r) 
{ 
    if (p < r) { 
     int q; 
     q = (p+r)/2 ; 
     mergesort(a,p,q); 
     mergesort(a,q+1,r); 
     merge(a,p,q,r); 
    } 
} 

Answer 1

看起來你沒有明確定義mergesort參數的含義。在這裏，你的最後一個元素定位一個過去的數組的末尾：

mergesort(a,0,sizeof(a)/sizeof(int)); 

但在這裏，

mergesort(a,p,q); 
mergesort(a,q+1,r); 

Q似乎是在數組中的最後一個元素。如果你的代碼遵循第一個，你將忘記實際排序值q。如果它跟在第二個之後，那麼您將嘗試對數組末尾的垃圾值進行排序。

Answer 2

如果要包括a[r]或沒有，你必須選擇。這裏你的選擇不一致，因此錯誤。

這裏是一個很好的代碼（我不包括a[r]）：

#include <stdio.h> 
#include <stdlib.h> 
#include <limits.h> 

void mergesort(int a[], int p, int r); 

void merge(int a[], int p, int q, int r) 
{ 
    int *left, *right; 
    int i,j,k,l,n1,n2; 
    n1 = q-p; 
    n2 = r-q; 
    left = malloc(sizeof(int)*(n1+1)); 
    right = malloc(sizeof(int)*(n2+1)); 
    for (i = 0; i < n1; i++) { 
     left[i] = a[p+i]; 
    } 
    for (j = 0; j < n2; j++) { 
     right[j] = a[q+j]; 
    } 
    left[n1] = INT_MAX; 
    right[n2] = INT_MAX; 
    i = 0; 
    j = 0; 
    for (k = p; k < r; k++) { 
     if (left[i] <= right[j]) { 
      a[k] = left[i]; 
      i++; 
     } 
     else { 
      a[k] = right[j]; 
      j++; 
     } 
    } 
    free(left); 
    free(right); 
    return ; 
} 

int main(int argc, char* argv[]) 
{ 
    int i; 
    int a[] = {5,2,4,7,1,3,2,6} ; 
    mergesort(a,0,sizeof(a)/sizeof(int)); 
    for (i = 0; i < sizeof(a)/sizeof(int); i++) { 
     printf("%d\n",a[i]); 
    } 
    return 0; 
} 

void mergesort(int a[], int p, int r) 
{ 
    if (r-p > 1) { 
     int q; 
     q = (p+r)/2 ; 
     mergesort(a,p,q); 
     mergesort(a,q,r); 
     merge(a,p,q,r); 
    } 
} 

Answer 3

不應該

mergesort(a,0,sizeof(a)/sizeof(int)); 

是

mergesort(a,0,sizeof(a)/sizeof(int)-1); 

？

考慮你做

n1 = q-p+1; 

等

有幾乎可以肯定是一個差一錯誤的地方在這裏。