简单的合并排序在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＃

回答

相关问题