合并排序的列表

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项目。所以继续合并排序来解决你的问题。

请查阅合并排序，这是一个分而治之算法，并理解它。那么你将能够轻松解决这个问题。