C＃功能快速排序失败

Question

我想实现使用C＃使用LINQ的功能风格的快速排序，并且此代码随机工作/不工作，我不明白为什么。
重要提醒：当我在数组或列表上调用它时，它工作正常。可是，在一个未知的 - 什么 - 它，真的，是IEnumerable的，它会疯狂（失去价值或崩溃，通常，有时作品。）
代码：

public static IEnumerable<T> Quicksort<T>(this IEnumerable<T> source) 
     where T : IComparable<T> 
    { 
     if (!source.Any()) 
      yield break; 
     var pivot = source.First(); 
     var sortedQuery = source.Skip(1).Where(a => a.CompareTo(source.First()) <= 0).Quicksort() 
          .Concat(new[] { pivot }) 
          .Concat(source.Skip(1).Where(a => a.CompareTo(source.First()) > 0).Quicksort()); 
     foreach (T key in sortedQuery) 
      yield return key; 
    } 

你能找到的任何故障这会导致这个失败？

编辑：一些更好的测试代码：

 var rand = new Random(); 
     var ienum = Enumerable.Range(1, 100).Select(a => rand.Next()); 
     var array = ienum.ToArray(); 
     try 
     { 
      array.Quicksort().Count(); 
      Console.WriteLine("Array went fine."); 
     } 
     catch (Exception ex) 
     { 
      Console.WriteLine("Array did not go fine ({0}).", ex.Message); 
     } 
     try 
     { 
      ienum.Quicksort().Count(); 
      Console.WriteLine("IEnumerable went fine."); 
     } 
     catch (Exception ex) 
     { 
      Console.WriteLine("IEnumerable did not go fine ({0}).", ex.Message); 
     } 

Answer 1

一些枚举情况下，如由返回的LINQ to SQL或实体框架查询，仅设计进行一次迭代。您的代码需要多次迭代，并且会在这些类型的实例上崩溃或行为异常。你必须首先用ToArray()或类似的方法实现这些枚举。

您还应该重复使用该pivot，以便您不必为第一个元素和其余元素进行迭代。这可能不会完全解决问题，但它会在某些情况下帮助：（您还没有通过sortedQuery需要迭代 - 只返回它，它已经是一个IEnumerable<T>）

public static IEnumerable<T> Quicksort<T>(this IEnumerable<T> source) 
    where T : IComparable<T> 
{ 
    if (!source.Any()) 
     return source; 
    var pivot = source.First(); 
    var remaining = source.Skip(1); 
    return remaining 
     .Where(a => a.CompareTo(pivot) <= 0).Quicksort() 
     .Concat(new[] { pivot }) 
     .Concat(remaining.Where(a => a.CompareTo(pivot) > 0).Quicksort()); 
} 

在相关说明中，为什么您觉得需要重新实现此功能？ Enumerable.OrderBy已经为你做。

---

响应更新：

你的测试失败，因为测试是错误，而不是算法。

Random是一个非确定性的输入源，正如我上面所解释的，排序方法需要在同一个序列上执行多次迭代。如果序列是完全随机的，那么在随后的迭代中将得到不同的值。本质上，你正试图快速排序一个元素不断变化的序列！

如果您希望测试成功，您需要使输入一致。使用种子随机数发生器：

static IEnumerable<int> GetRandomInput(int seed, int length) 
{ 
    Random rand = new Random(seed); 
    for (int i = 0; i < length; i++) 
    { 
     yield return rand.Next(); 
    } 
} 

然后：

static void Main(string[] args) 
{ 
    var sequence = GetRandomInput(248917, 100); 
    int lastNum = 0; 
    bool isSorted = true; 
    foreach (int num in sequence.Quicksort()) 
    { 
     if (num < lastNum) 
     { 
      isSorted = false; 
      break; 
     } 
     lastNum = num; 
    } 
    Console.WriteLine(isSorted ? "Sorted" : "Not sorted"); 
    Console.ReadLine(); 
} 

它会回来的排序。