如何使用 LINQ 执行合并排序？

Question

假设您有两个 IEnumerbale 对象。我们如何合并它们（在某些情况下，例如合并排序中的合并......）并创建一个唯一的IEnumerable？我用 Zip 尝试过，但在 Zip 中，两个列表大小应该相等（也许您没有遇到异常，但也许我们丢失了一些数据。）

此外，我通过使用 Enumerable 进行尝试。 Range(...).Select(...) 但我没有得到可接受的结果。

此外，我的问题与使用 Union 或 这个 完全不同，事实上，正如我所说，就像合并排序中的合并一样，我喜欢保留列表顺序（实际上只是想填补第一个列表中的一些空白）。

使用 for 循环很容易处理它，但我看不到任何完整的 linq 方式。

编辑：

Sample input:

lst1 = {5,10,12}
lst2 = {7,9,16,20,25}

result: {5,7,9,10,12,16,20,25}

这可以通过 O(n + m) 中的 for 循环和两个指针来完成，但我正在寻找 O(n+ m)

for循环解决方案：

        var lst1 = new List<int> { 5, 10, 12 };
        var lst2 = new List<int> { 7, 9, 16, 20, 25 };

        var result = new List<int>();

        int j = 0;
        for (int i = 0; i < lst1.Count; i++)
        {
            while (j < lst2.Count && lst2[j] < lst1[i])
            {
                result.Add(lst2[j]);
                j++;
            }
            result.Add(lst1[i]);
        }

        while (j < lst2.Count)
        {
            result.Add(lst2[j]);
            j++;
        }
        Console.WriteLine(string.Join(",", result.ToArray()));

Answer 1

LINQ中没有这样的方法。而且我认为不可能结合现有的方法来完全完成您想要的事情（如果是的话，那就太复杂了）。

但自己实现这样的方法并不难：

static IEnumerable<T> Merge<T>(this IEnumerable<T> first,
                               IEnumerable<T> second,
                               Func<T, T, bool> predicate)
{
    // validation ommited

    using (var firstEnumerator = first.GetEnumerator())
    using (var secondEnumerator = second.GetEnumerator())
    {
        bool firstCond = firstEnumerator.MoveNext();
        bool secondCond = secondEnumerator.MoveNext();

        while (firstCond && secondCond)
        {
            if (predicate(firstEnumerator.Current,  secondEnumerator.Current))
            {
                yield return firstEnumerator.Current;
                firstCond = firstEnumerator.MoveNext();
            }
            else
            {
                yield return secondEnumerator.Current;
                secondCond = secondEnumerator.MoveNext();
            }
        }

        while (firstCond)
        {
            yield return firstEnumerator.Current;
            firstCond = firstEnumerator.MoveNext();
        }

        while (secondCond)
        {
            yield return secondEnumerator.Current;
            secondCond = secondEnumerator.MoveNext();
        }
    }
}

你可以这样使用它：

lst1.Merge(lst2, (i, j) => i < j)

Answer 2

System.Linq.Enumerable 中没有 Merge 方法。如果你想要一个，你必须编写它（使用 for 循环和yield 语句）。

与许多“仅通过 linq”问题一样 - 您应该假设每个 linq 方法都由您自己编写的一些简单的旧 .NET 代码支持。

---

这是一个未经测试的徒手非通用实现

public static IEnumerable<int> Merge
(
this IEnumerable<int> source1,
IEnumerable<int> source2
)
{
  using(Enumerator<int> e1 = source1.GetEnumerator())
  {
    bool more1 = e1.MoveNext();
    using(Enumerator<int> e2 = source2.GetEnumerator()
    {
      bool more2 = e2.MoveNext();

      while (more1 && more2)
      {
        int v1 = e1.Current;
        int v2 = e2.Current;
        if (v1 < v2)
        {
          yield return v1;
          more1 = e1.MoveNext();
        }
        else
        {
          yield return v2;
          more2 = e2.MoveNext();
        }

      }
      while (more1 && ! more2)
      {
        yield return e1.Current;
        more1 = e1.MoveNext();
      }
      while (more2 && ! more1)
      {
        yield return e2.Current;
        more2 = e2.MoveNext();
      }
    }
  }
}

Answer 3

使用 LINQ 方法 Concat() http://msdn. microsoft.com/en-us/library/bb302894.aspx