C#功能快速排序失败

Question

我正在尝试使用linq使用C#实现一个功能样式的快速排序,这个代码随机工作/不起作用,我无法弄清楚为什么.
重要的是:当我在数组或列表上调用它时,它工作正常.但是在一个未知的 - 它真的是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返回到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<T>.)

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

对更新的回应:

您的测试失败是因为您的测试错误,而不是算法.

Random是一个非确定性的输入源,正如我上面所解释的,sort方法需要在同一序列上执行多次迭代.如果序列是完全随机的,那么它将在后续迭代中获得不同的值.从本质上讲,您正在尝试快速排序其元素不断变化的序列!

如果您希望测试成功,则需要使输入保持一致.使用种子作为随机数生成器:

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

它将重新排序.