合併排序的列表

Question

我想拿出一個分割和征服算法來合併j個排序的列表與n個元素，但我卡住了;我不知道如何將這個問題分成更小的子問題。我希望合併算法的效率更高，如下所示：

合併前兩個列表;然後將結果列表與第三個列表合併;然後將結果列表與第四個列表進行合併，這需要O（j * jn）。

Answer 1

U可以做到這一點爲O（j *日誌（J）n）的時間

while(n!=1) 
    for i=0 to n/2 
     merge list(i) with list list(n) 
    n = n/2 

這樣ü合併全團分成兩人一組，然後對等

Answer 2

不知道對和爲什麼你需要分而治之才能做到這一點。你可以只創建一個大名單無序然後使用內置的排序排序的大名單這將是O（JN *日誌（JN））

List<int> returnList(List<List<int>> lists) 
    { 
     List<int> ret = new List<int>(); 
     for(int i=0;i<lists.Length;i++) 
     { 
      for(int j=0;j<lists;j++) 
      { 
       ret.Add(lists[i][j]);    
      } 
     } 
     ret.Sort(); 
    } 

Answer 3

這是沒有從標準歸併排序不同。考慮包含未排序項目的大小爲jn的列表。在大小爲jn的項目列表上合併排序的log(n)迭代之後，您將在每個列表中有j排序列表和n項目。所以繼續合併排序來解決你的問題。

請查閱合併排序，這是一個分而治之算法，並理解它。那麼你將能夠輕鬆解決這個問題。