簡單的合併排序在C＃

我一直在做排序算法的小修訂，並遇到了合併排序。我編寫了我的代碼，並在最後一個小時修改了它，確定它爲什麼還沒有工作。我得到標準的StackOverFlow異常。任何人都可以告訴我算法有什麼問題嗎？提前致謝。在這裏我已經設法到目前爲止寫：簡單的合併排序在C＃

public Int32[] MergeSort(Int32[] array) 
{ 
    int counter = 0; 
    if (array.Length == 0) { return array; } 
    int mid = array.Length/2; 
    Int32[] leftHalf = new Int32[mid+1]; 
    Int32[] rightHalf = new Int32[mid+1]; 
    for (int i = 0; i < mid; i++) { 
     leftHalf[i] = array[i]; 
    } 
    for (int j = mid; j < array.Length; j++) { 
     rightHalf[counter] = array[j]; 
     counter++; 
    } 
    counter = 0; 
    MergeSort(leftHalf); 
    MergeSort(rightHalf); 
    return SortAndMerge(leftHalf,rightHalf); 
} 

public Int32[] SortAndMerge(Int32[] left, Int32[] right) { 
    Int32[] myResult = new Int32[left.Length+right.Length]; 
    while (left.Length > 0 || right.Length > 0) { 
     if (left.Length > 0 && right.Length > 0) 
     { 
      if (left[0] <= right[0]) 
      { 
       myResult[myResult.Length] = left[0]; 
       int toRemoveIndex = Array.IndexOf(left, left[0]); 
       left = left.Where((x, y) => y != toRemoveIndex).ToArray(); 
      } 
      else 
      { 
       myResult[myResult.Length] = right[0]; 
       int toRemoveIndex = Array.IndexOf(right, right[0]); 
       right = right.Where((z, g) => g != toRemoveIndex).ToArray(); 
      } 

     } 
     else if (left.Length > 0) 
     { 
      myResult[myResult.Length] = left[0]; 
      int toRemoveIndex = Array.IndexOf(left, left[0]); 
      left = left.Where((x, y) => y != toRemoveIndex).ToArray(); 
     } 
     else if (right.Length > 0) { 
      myResult[myResult.Length] = right[0]; 
      int toRemoveIndex = Array.IndexOf(right, right[0]); 
      right = right.Where((x, y) => y != toRemoveIndex).ToArray(); 
     } 
    } 
    return myResult; 
}

來源

2017-04-10 Rustam Umarov

你可以解釋'counter'在'MergeSort'函數中做了什麼？...我的意思是我知道它在做什麼，但爲什麼不用'rightHalf [j - mid]'而不是'rightHalf [counter] '......可能會使它更清楚嗎？ –

對不起，要問魯斯塔姆，但使用這麼多嵌套的if，是否真的需要？在甚至爲什麼會出現SO錯誤之前，我們是否應該考慮擺脫這些嵌套的if，作爲算法修訂的一部分，我將看看算法是否確實需要這種隱藏性。 – Arjang

調試器會給你一個堆棧跟蹤，你可以逐行通過代碼。這會給你很多關於發生的事情的信息，特別是在永久循環中。 –

if (array.Length == 0) return;

這是不正確的，這樣的例外，因爲你總是創建數組這樣。

Int32[] leftHalf = new Int32[mid+1];

最小長度爲1

退房正確的歸併排序算法在這裏。

https://en.wikipedia.org/wiki/Merge_sort#Algorithm

來源

2017-04-10 04:38:26

這是正確的 –

正確，雖然，謝謝，但它不能解決問題。 –

你介意重構？爲什麼不使用zip 這裏將樣品從MSDN

int[] numbers = { 1, 2, 3, 4 }; 
string[] words = { "one", "two", "three" }; 
var numbersAndWords = numbers.Zip(words, (first, second) => first + " " + second); 
foreach (var item in numbersAndWords) 
Console.WriteLine(item);

此代碼產生以下輸出：

1一個

2兩

還有LINQ爲了排序。

來源

2017-04-10 04:44:01 Ariwibawa

我正在考慮實施合併排序，這就是爲什麼ZIP不適合我。不管怎樣，謝謝。 –

簡單的合併排序在C＃

回答

相關問題