使用printf時Mergesort輸出更改

Question

嘗試在C中構建mergesort作爲練習時，我遇到了一個奇怪的問題，其中算法的輸出隨printf的存在而變化。讓我進一步闡述它。我有一個「MergeSort.h」文件中，我有我的歸併算法如下：

#ifndef _MSORT_H_ 
#define _MSORT_H_ 

void merge(int a[],int lo,int mi,int hi){ 
    int n1 = (mi - lo) +1; 
    int n2 = hi - mi; 
    int left[n1]; 
    int right[n2]; 
    int i; 
    int j; 
    int k; 
    for(i = 0;i < n1;i++){ 
     left[i] = a[lo+i]; 
    } 
    for(j = 0;j < n2;j++){ 
     right[j] = a[mi+j+1]; 
    } 
    i = 0; 
    j = 0; 
    for(k = lo;k <= hi;k++){ 
     if(left[i] < right[j]){ 
      a[k] = left[i]; 
      i = i + 1; 
     }else{ 
      a[k] = right[j]; 
      j = j+1; 
     } 
    } 

} 

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

void msortex(int a[],int size){ 
    msorthelper(a,0,size-1); 
    int counter; 
    for(counter = 0;counter < size;counter++){ 
     printf(" %d ",a[counter]); 
    } 
} 
#endif 

我有相應排序測試儀sorttester.c：

#include <stdio.h> 
#include "mergesort.h" 

int main(){ 

    int out[] = {8,1,6}; 
    msortex(out,3); 

} 

從運行sorttester輸出如下：

現在，這裏的有趣的部分，當我把任何printf語句放到合併開始時，就會生成正確的輸出。下面是一個例子：

#ifndef _MSORT_H_ 
    #define _MSORT_H_ 

    void merge(int a[],int lo,int mi,int hi){ 
     printf("Hello\n"); 
     int n1 = (mi - lo) +1; 
     int n2 = hi - mi; 
     int left[n1]; 
     int right[n2]; 
     .................Rest of the code..... 

現在的輸出是：

HelloHello 1 6 8

這是陣列8 6 1.

能否正確排序的順序有人告訴我，我在這裏可能會做錯什麼，導致輸出由於printf的存在而急劇增加？

感謝

Answer 1

看一看的代碼的合併部分：

for(k = lo;k <= hi;k++){ 
    if(left[i] < right[j]){ 
     a[k] = left[i]; 
     i = i + 1; 
    }else{ 
     a[k] = right[j]; 
     j = j+1; 
    } 
} 

讓我們假設

left[] = {1, 2} 
right[] = {3, 4, 5} 

經過2次迭代的合併循環（k）的「價值我「將是2.從現在開始，你會嘗試比較

left[2] < right[j] 

這是無效的，因爲左[2]將參考一些隨機存儲器（左陣列大小僅爲2，那麼索引2犯規的元件存在，只有0和1）

因此，如果添加看守i和j值，例如通過首先將條件改爲：

if(i != n1 && (j == n2 || left[i] < right[j])){ 

你應該沒問題。

無論如何，我也要告訴你，你不應該與沒有const的，像值聲明數組的大小：

int left[n1]; 
int right[n2]; 

它實際上是由標準禁止的。你應該動態地分配它，使用向量（如果是C++）或者用絕對大小（最大n值）聲明它們是全局的。