如何控制合併排序我的算法的堆棧溢出

嗨，那裏我仍然無法找出爲什麼我的代碼給我堆棧溢出它的接縫，我的合併排序算法的低和高界限改變某處不應該做的。。如何控制合併排序我的算法的堆棧溢出

int[] arr = new int[10]; 
    private void button1_Click(object sender, EventArgs e) 
    { 
     merge_sort(0, 9); 
    } 

    private void merge_sort(int left, int right) 
    { 
     if (left > right) 
      merge(left, right, (left + right)/2); 
     else 
      merge_sort((left + right)/2 + 1, right); 
     merge_sort(left, (left + right)/2); 

    } 
    void merge(int low, int high, int mid) 
    { 
     int i, j, k, t; 
     j = low; 
     for (i = mid + 1; i <= high; i++) 
     { 
      while (arr[j] <= arr[i] && j < i) 
       j++; 
      if (j == i) 
       break; 
      t = arr[i]; 
      for (k = i; k > j; k--) 
       arr[k] = arr[k - 1]; 
      arr[j] = t; 
     } 
    }

來源

2012-05-17 John

它總是冷靜地看到在這裏 – user12345613

一個實際的堆棧溢出問題，從高層次的代碼看起來不正確的。合併排序通常採用分而治之的形式'merge_sort（left）'然後'merge_sort（right）'然後調用'merge（）'。 [參考這裏]（http://en.wikipedia.org/wiki/Merge_sort） – Blastfurnace

你的意思是，第一次merge_sort（左）完成合並（）應運行和merge_sort（右）相同！ – John

你有

merge_sort((left + right)/2 + 1, right);

，我認爲應該是

merge((left + right)/2 + 1, right);

來源

2012-05-17 11:10:02

對不起，你能解釋更多 – John

您的merge_sort recrusive方法將永遠不會結束，因爲最後一行總是被調用再次調用merge_sort ...這是無限遞歸，應該引起stackoverflow。

private void merge_sort(int left, int right) 
{ 
    if (left > right) 
    merge(left, right, (left + right)/2); 
else 
    merge_sort((left + right)/2 + 1, right); 
merge_sort(left, (left + right)/2); //<-- this is your problem! 
}

我認爲（也許）你想這樣做，而不是：

private void merge_sort(int left, int right) 
{ 
    if (left > right) 
    merge(left, right, (left + right)/2); 
else 
{ 
    merge_sort((left + right)/2 + 1, right); 
    merge_sort(left, (left + right)/2) 
} 
}

來源

2012-05-17 11:13:18

如果你總是使用大括號，事情會更簡單...一堆風格指南建議總是使用大括號... –

好吧，這是一個風味的問題..如果你把3條線，每次你可以有1行，你會得到更長的方法..我不能說我更喜歡.. –

我改變了這樣的代碼。堆棧溢出問題已解決，但我沒有得到正確的結果！

private void merge_sort(int left, int right) 
    { 
     if (left > right) 
      merge(left, right, (left + right)/2); 
     else 
     { 
      merge_sort((left + right)/2 + 1, right); 
      merge(left, right, (left + right)/2+1); 

     } 

    }

最近我發現瞭如何通過改變我的代碼部分來控制它，但我還是不明白是什麼問題!!!! 這裏的變化：

private void merge_sort(int low, int high) 
    { 

int mid; 
     if (low != high) 
     { 
      mid = (low + high)/2; 
      merge_sort(low, mid); 
      merge_sort(mid + 1, high); 
      merge(low, mid, high); 
     }

來源

2012-05-17 19:43:07 John

你是否錯過了一些花括號？你的代碼縮進__implies__對'merge_sort'和'merge'的調用都在'if'語句的'else'分支中。如果沒有大括號，最後一次調用'merge'就不在'if/else'之外。 – Blastfurnace

這個問題不僅僅是大括號，它不僅僅是一個簡單的大括號，它並不會對它的排列進行排序，事實上它的接縫是低位和高位在某處不應該改變的地方。 – John

如何控制合併排序我的算法的堆棧溢出

回答

相關問題