合并排序列表

Question

我正试图想出一个分而治之的算法来合并j个排序列表和n个元素，但我被卡住了；我不知道如何把这个问题分成更小的子问题。我希望合并算法更高效，如下所示：

合并前两个列表；然后将结果列表与第三个列表合并；然后将结果列表与第四个列表合并，以此类推，该列表取O（j*jn）。

Answer 1

这与标准的合并排序没有什么不同。考虑一个带有未排序项的sizejn列表。在log（n）对sizejn项列表进行合并排序迭代后，您将拥有在每个列表中具有n项的j排序列表。所以继续使用合并排序来解决您的问题。

请查阅合并排序，这是一种分治算法，并理解它。这样你就能很容易地解决这个问题了。

Answer 2

不知道为什么你需要分而治之来实现这一点。您只需创建一个无序的大列表，然后使用内置排序对大列表进行排序，它将是O（jn*Log（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

你可以在O（j*log（j）n）时间内完成

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

这样你就可以把整个团队合并成一对，然后再合并成一对对，依此类推