使用IEnumerable实现QuickSort的复杂性是什么?

这个 IEnumerable<> 不缓存。如果它由集合支持(如新的 int[5].AsEnumerable() )然后你可以重复使用它多少次,但是 理论上,可以一次生成一个零碎的元素,在内存中,只有当前的元素,而之前的元素被遗忘了。不能保证枚举两次 IEnumerable<gt; 将返回相同的数据,也不可能枚举两次。你链接的问题很愚蠢,表明海报不知道他在说什么。

这个 QuickSort(IEnumerable<int> ints) 建议有一个参数 IEnumerable<int> ints . 该方法没有任何外部保证 IEnumerable<int>整数 可以枚举两次,或者即使访问一次也不会导致O(N)操作。

现在。。。 .First() 可能是O(N)操作,或者更糟,例如,如果必须订购支持集合…如果你 QuickSort(new[] { 5, 4, 3, 2, 1}.OrderBy(x => x)) 然后 pars.First() 执行后需要等待 OrderBy() 待执行,以及 排序依据() 必须先看看整个背衬 IEnumerable<gt; (the new[] { } )对其进行排序(因此至少为o(n))

“有趣”的例子 First() 那是O(N)o n a IEnumerable<gt; 每次执行时都会给出不同的结果。

private static int seed = 0;
public static IEnumerable<int> GetSomeInts()
{
    var rnd = new Random(seed++);

    for (int i = 0; i < 10; i++)
    {
        Console.Write(".");
        yield return rnd.Next(100000);
    }
}

for (int i = 0; i < 10; i++)
{
    Console.WriteLine(GetSomeInts().OrderBy(x => x).First());
}

你可以看到 O(N) 从打印的“.”号开始。尝试删除 排序依据() 观察结果。关于这个事实 IEnumerable<gt; 每次执行时都会返回不同的结果…好。。。有一个 for 循环:-)尝试查看结果。