我在這個C＃mergesort算法中做錯了什麼？

Question

對於學校任務，我必須實施mergesort。

我用這個代碼做的伎倆：

static int[] MergeSort(int[] C) 
    { 
     int left = 0; 
     int right = C.Length; 
     int middle = (left + right)/2; 
     int[] A, B; 
     A = new int[middle]; 
     B = new int[middle]; 

     if (C.Length == 0 || C.Length == 1) 
     { 
      return C; 
     } 
     else 
     { 
      for (int i = left; i < middle; i++) 
      { 
       A[i] = C[i]; 
       B[i] = C[middle + i]; 
      } 

      MergeSort(A); 
      MergeSort(B); 
      return Merge(A, B, C); 
     } 
    } 

    static int[] Merge(int[] A, int[] B, int[] C) 
    { 
     int i, j, k; 
     i = j = k = 0; 
     int n = A.Length; 
     int m = B.Length; 
     int c = C.Length; 
     int middle = C.Length/2; 

     while (i < n && j < m) 
     { 
      if (A[i] < B[j]) 
      { 
       C[k] = A[i]; 
       i++; 
      } 
      else 
      { 
       C[k] = B[j]; 
       j++; 
      } 
      k++; 

      if (i == n) 
      { 
       for (int b = i; b < B.Length; b++) 
       { 
        C[middle + b] = B[b]; 
       } 
      } 
      else 
      { 
       for (int a = i; a < A.Length; a++) 
       { 
        C[middle + a] = A[a]; 
       } 
      } 
     } 

     return C; 
    } 

它不適合很多不同行的工作，雖然。我已經調試過並檢查約束是否有問題，但我似乎無法找到問題。

在此先感謝！

Answer 1

除了Guffa回答，您應該編輯合併方法的代碼像這樣：

while (i < n && j < m) 
    { 
     if (A[i] < B[j]) 
     { 
      C[k] = A[i]; 
      i++; 
     } 
     else 
     { 
      C[k] = B[j]; 
      j++; 
     } 
     k++; 
    } 
    if (i == n) 
    { 
     for (int b = j; b < B.Length; b++) 
     { 
      C[k++] = B[b]; 
     } 
    } 
    else 
    { 
     for (int a = i; a < A.Length; a++) 
     { 
      C[k++] = A[a]; 
     } 
    } 

雖然循環塊應該在k ++之後結束並且在第一個for循環中，您應該用j代替i來初始化b。另外，要注意C數組的下一個元素的索引，它是k，不一定是中間值+ a或b。

Answer 2

我發現的第一件事情是你如何在陣列分成兩個：

A = new int[middle]; 
B = new int[middle]; 

如果長度甚至沒有，你會留出的最後一個項目。你應該有：

A = new int[middle]; 
B = new int[right - middle]; 

那麼你可以使用單獨的迴路對他們來說，因爲它們的長度可以是不同的：

for (int i = left; i < middle; i++) { 
    A[i - left] = C[i]; 
} 
for (int i = middle; i < right; i++) { 
    B[i - middle] = C[i]; 
}