另一个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

回答

相关问题