Как выполнить сортировку слиянием с помощью LINQ? - PullRequest
Новая
       0

Как выполнить сортировку слиянием с помощью LINQ?

4 голосов
/ 10 октября 2011

Предположим, у вас есть два IEnumerbale объекта. Как мы можем объединить их (в некоторых условиях, например, объединить в сортировку слиянием ...) и создать уникальный IEnumerable? Я пробовал это с Zip, но в Zip два размера списка должны быть равны (возможно, вы не получили исключение, но, возможно, у нас потерялись некоторые данные.)

Кроме того, я пробую это с помощью Enumerable.Range (...). Выберите (...), но я не получил приемлемый результат.

Кроме того, мой вопрос полностью отличается от использования Union или этого , на самом деле, как я сказал, вроде слияния в сортировке слиянием, мне нравится сохранять порядок списков (на самом деле просто хочу сначала заполнить несколько пробелов список).

С циклом for легко справиться, но я не вижу полного пути linq.

Edit: 

Sample input:

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

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

это можно сделать с помощью цикла for и двух указателей в O(n + m), но я ищу решение linq в O(n+m)

для петлевого решения: 

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

Ответы [ 3 ]

11 голосов
/ 11 октября 2011

В 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)
7 голосов
/ 11 октября 2011

В System.Linq.Enumerable нет метода слияния. Если вы хотите его, вы должны написать его (с циклом 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();
      }
    }
  }
}
0 голосов
/ 11 октября 2011

Использовать метод LINQ Concat() http://msdn.microsoft.com/en-us/library/bb302894.aspx

...