另一個Quicksort stackoverflow

所以我一直試圖自己實現一個quicksort，只是爲了從中學到一些東西，但它也會產生一個stackoverflowexception，但我似乎無法找到原因是什麼。另一個Quicksort stackoverflow

有人可以給我一個線索嗎？

public void Partition(List<int> valuelist, out List<int> greater, out List<int> lesser) 
     { 
      lesser = new List<int>(); // <-- Stackoverflow exception here! 
      greater = new List<int>(); 

      if (valuelist.Count <= 1) 
       return; 

      pivot = valuelist.First(); 

      foreach (int Element in valuelist) 
      { 
       if (Element <= pivot) 
        lesser.Add(Element); 
       else 
        greater.Add(Element); 
      } 
     } 

     public List<int> DoQuickSort(List<int> list) 
     { 
      List<int> great; 
      List<int> less; 

      Partition(list, out great, out less); 

      DoQuickSort(great); 
      DoQuickSort(less); 

      list.Clear(); 
      list = (List<int>)less.Concat(great); 

      return list; 

     }

來源

2010-01-19 Tony The Lion

這不就是最好的，只是爲了找到給它一些小數據進行排序，並通過調試器通過它來查看邏輯不正確的位置？ – Toad 2010-01-19 13:10:00

我不認爲任何依靠創建大量集合和複製大量值的排序算法都可以稱爲「快速」。你應該重新命名它「保證儘可能緩慢的內存密集型日誌。」 – Will 2010-01-19 13:12:06

@reinier：依靠調試器來發現你的邏輯錯誤是非常懶惰的。有時候這是不可避免的，但是如果沒有調試器的幫助，能夠找到錯誤要好得多。 – 2010-01-19 13:16:33

你不把你的遞歸調用任何條件DoQuicksort，所以它永遠不會停止遞歸，導致堆棧溢出。如果它包含多個元素，則只應在列表上調用DoQuicksort。

編輯：正如威爾在他的評論中所說，這是一個非常緩慢的方法來「快速排序」。您應該查看Wikipedia的Quicksort article中提到的就地分區算法。

來源

2010-01-19 13:10:43

你正在做一個無限循環那裏

DoQuickSort(great);

你需要一種方式來擺脫一個標誌或條件

編輯該循環
我會加在調試模式下，使用默認設置時，在發生異常前，您只能達到10,000到16,000次遞歸調用，在發佈模式下，您只能達到50,000到80,000次之間，都取決於執行的實際代碼。

如果您使用大量值玩，則可能需要使用Stack對象來管理遞歸調用。

示例代碼，以查看崩潰之前的調用次數;
（調試; 14210呼叫，釋放80071呼叫）

static int s = 1; 
    static void Main(string[] args) 
    { 
     o(); 
    } 

    static void o() 
    { 
     s++; 
     Console.WriteLine(s.ToString()); 
     o(); 
    }

來源

2010-01-19 13:08:09 Fredou

正確 - 因爲pivot是作爲'great'中的第一個條目放置的，所以每次你都會使用同一個pivot。 – 2010-01-19 13:13:34

是的，在DoQuickSort方法中沒有任何條件檢查。 Partition方法足夠聰明，可以知道何時退出，但這種檢查並沒有在調用者中完成。 – Will 2010-01-19 13:13:56

我認爲你的代碼中的問題之一是你在分區列表時保留了pivot值。這意味着您將遇到所有值分割爲更大或更小的情況，並且分區將停止工作。這實際上不會讓你拆分其中一個列表，因此分區方法中的退出條件永遠不會滿足。

你應該選擇一個支點值，從列表刪除主元（這部分缺失在你的代碼），分區之前它在大於和小於列表，排序的（遞歸），然後串聯少列表，主元素（這在你的代碼中自然也是缺少的）和更大的列表。

我可以發佈一個更新，工作，代碼示例，但因爲你是在「學習模式」，我將它留給自己，直到你問它:)

來源

2010-01-19 13:28:09

+1感謝您的解釋！ – 2010-01-19 13:32:22

每次通過它時，我是否刪除一個新的數據透視值？並在分區結尾的正確位置再次添加它？困惑？！？ – 2010-01-19 13:54:24

@Tony：我認爲維基百科文章中的僞代碼樣本可能會幫您理清：http://en.wikipedia.org/wiki/Quicksort#Algorithm – 2010-01-19 14:03:46

另一個Quicksort stackoverflow

回答

相關問題