C# 函数式快速排序失败

Question

我正在尝试使用 C# 使用 linq 以函数式风格实现快速排序，此代码随机工作/不工作，我不明白为什么。
值得一提的是：当我在数组或列表上调用它时，它工作得很好。但在未知的 IEnumerable 上，它会变得疯狂（通常会丢失值或崩溃。有时会起作用。）
代码：

 public static IEnumerable; Quicksort（此 IEnumerable 来源）
        其中T：IComparable
    {
        if (!source.Any())
            产量突破；
        var hub = source.First();
        var SortedQuery = source.Skip(1).Where(a => a.CompareTo(source.First()) <= 0).Quicksort()
                          .Concat(new[] { 枢轴 })
                          .Concat(source.Skip(1).Where(a => a.CompareTo(source.First()) > 0).Quicksort());
        foreach（sortedQuery 中的 T 键）
            产量返回键；
    }

您能在这里找到导致此失败的任何错误吗？

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

 var rand = new Random();
        var ienum = Enumerable.Range(1, 100).Select(a => rand.Next());
        var array = ienum.ToArray();
        尝试
        {
            array.Quicksort().Count();
            Console.WriteLine("数组运行良好。");
        }
        catch（异常前）
        {
            Console.WriteLine("数组运行不正常 ({0})。", ex.Message);
        }
        尝试
        {
            ienum.Quicksort().Count();
            Console.WriteLine("IEnumerable 一切顺利。");
        }
        catch（异常前）
        {
            Console.WriteLine("IEnumerable 运行不正常 ({0})。", ex.Message);
        }

Answer 1

某些可枚举实例（例如 Linq to SQL 或实体框架查询返回的实例）仅设计为迭代一次。您的代码需要多次迭代，并且在这些类型的实例上会崩溃或表现奇怪。您必须首先使用 ToArray() 或类似方法具体化这些枚举。

您还应该重用该pivot，这样您就不必继续迭代第一个和剩余的元素。这可能无法完全解决问题，但在某些情况下会有所帮助：（

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

您也不需要遍历 sortedQuery - 只需返回它，它已经IEnumerable。）

在相关说明中，您为什么觉得需要重新实现此功能？ 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();
}

它将返回排序。