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(); 
} 

它會回來的排序。