sorting - 从n x m数组中按升序打印数字，其行已排序

我们有一个n x m矩阵，其行已排序，我们需要按升序打印矩阵中的数字。列不必排序。我想到的解决方案是简单地将矩阵中的行合并为单独的列表(基本上是合并排序中的合并步骤)，合并排序中的行需要O(n)。我想知道在这种情况下合并n个单独的数组的复杂性是什么。我以为会是O(n x m)，但我不确定。

另外，将数字升序打印的更好方法是什么？一次合并n个列表，还是一次合并2个列表，直到我们考虑所有行？

谢谢!

最佳答案

What would be complexity? Its all depends how do you merge N arrays of M size!
合并的复杂性:

合并两个排序的M大小数组按顺序进行。因此，此步骤的复杂度为O(2M)。

对于 N rows ，其中 each row is sorted 和包含M元素。

如果这样做(线性合并):

首先合并两行-您将获得中间2M size sorted array。

将2M array与另一个row of N size matix合并-您将获得3M size sorted array。

以这种方式合并takes N steps和complexity would be O(N*M)。

更好的方法(分治技术):

首先合并所有两对连续的两行(1,2)，(3,4)，这将为您提供N / 2对2M大小。在下一步中成对合并。如下所述。

首先将两行和merge all N/2 pairs first and merge them配对。
例如:双排(1,2);行(3,4); row(5,6)......您将获得= N/2 pairs each of 2M size。

现在在下一步中，make pair of two merged arrays each of size 2M from previous step然后合并它们-您将get N/4 sorted array of 4M size。((2M与其他2M数组的合并-> 4M且复杂度为O(2M + 2M)= O(4M))

逐步合并所有这些中间sorted arrays util you gets a single sorted array of size N*M。这一次的复杂度将为 M * N * log(N)作为总steps required is log(N)。

我想推荐您学习merge-sort and its complexity.

关于sorting - 从n x m数组中按升序打印数字，其行已排序，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13410763/