如何使用LINQ執行合併排序？

假設您有兩個IEnumerbale對象。我們如何合併它們（在某些情況下，例如合併排序中的合併...）並創建一個唯一的IEnumerable？我試着用Zip，但在Zip中，兩個列表大小應該是相等的（也許你沒有例外，但也許我們有一些數據丟失）。 ..）。選擇（...）但我沒有得到可接受的結果。另外，我的問題與使用Union或this one完全不同，事實上，正如我在合併排序中所說的那樣，我喜歡保留列表順序（實際上只是想填補第一個列表中的一些空白）。如何使用LINQ執行合併排序？

用for循環處理它很容易，但是我看不到任何完整的linq方式。

編輯：

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)但我在O(n+m)

尋找LINQ解決方案循環的解決方案：

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

來源

2011-10-10 Saeed Amiri

請詳細說明一下。如果'Union'不適合你，我不知道你在找什麼。 –

你的聯盟後你不能做OrderBy嗎？ – thekip

@John Saunders，假設最常見的問題，就像在這種情況下合併排序合併一樣，如果再次使用union，則應該調用OrderBy來合併結果，但它不適合mergesort情況。 –

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)

來源

2011-10-10 20:32:31 svick

對於迭代器實現的示例+1，如果我沒有得到任何好的linq我會接受這個。 –

-2

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

來源

2011-10-10 20:01:50

這不排序，但'var list3 = list1.Concat（list2）.OrderBy（i => i）;'確實。 – ChrisF

liho請參閱評論 –

@SaeedAmiri我沒有看到任何意味着Concat（）不是你需要的東西。如果你想對它進行分類，那麼在......之後做這個問題？ –

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

來源

2011-10-10 20:10:32

-2

與樣品的數據，我可以簡單地通過排序得到你的結果：

lst1.Concat(lst2).OrderBy(i => i)

究竟你通過合併的意思？如何合併？

來源

2011-10-10 20:24:57

在O（n + m）中完成合並，但已完成排序在O（（n + m）log（n + m）） –

@SaeedAmiri：O（（n + m）log（n + m））和'OrderBy（）'有什麼關係？ –

當我有兩個大小的列表（m，n）它需要這個時間（正常排序），並且orderby是某種排序。 –

對於一個現成的，現成的解決方案退房MoreLinq。

它提供了許多其他的IEnumerable擴展方法SortedMerge。

來源

2016-09-15 22:39:16

如何使用LINQ執行合併排序？

回答

相關問題