如何对一个m x n矩阵进行排序，其中所有m行都已排序，n列也都已排序？

Question

给定一个有m行n列的矩阵，其中每个行和列都是已排序的。如何高效地对整个矩阵进行排序？

我知道一个运行时间为O(m n log(min(m,n))的解决方案。我正在寻找更好的解决方案。

我所知道的方法基本上是每次取2行/列并应用合并操作。

以下是一个例子：

[[1,4,7,10],

 [2,5,8,11],

 [3,6,9,12]]

输入矩阵的每一行和每一列都是已排序的。

期望的输出结果是：

[1,2,3,4,5,6,7,8,9,10,11,12]

另一个例子：

[[1, 2, 3, 3, 4, 5, 6, 6, 7, 7],

 [1, 2, 4, 6, 7, 7, 8, 8, 9,10],

 [3, 3, 4, 8, 8, 9,10,11,11,12],

 [3, 3, 5, 8, 8, 9,12,12,13,14]]

- Anil Katti

---

这个矩阵中的单元格最高值已知吗？内存复杂度是否是一个问题？ - Neowizard

这个问题比较模糊 - 尝试为一个小的 m x n 矩阵给出一个前/后的例子。 - Paul R

@Paul [(1, 4, 8), (2, 9, 11), (3, 12, 14)] - khachik

在你的例子中，给定列的所有元素始终高于前一列中的任何元素，这总是正确的吗？ - Orbling

@Anil Katti：很好，否则解决方案将是O(mn)，我想你已经看到了！ - Orbling

Answer 1

我认为在一般情况下，你不可能比Ω(m n log(min(m, n)))更快地完成它。

假设（没有失去一般性），m < n。那么你的矩阵看起来像这样:

每个圆圈都是一个矩阵条目，每个箭头表示一个已知的顺序关系（箭头源处的条目小于箭头终点处的条目）。

要对矩阵进行排序，我们必须解决所有未知的顺序关系，其中一些显示在这里的灰色框中:

排序所有这些框需要:

2 Σ_{k < m} Ω(k log k) + (n - m + 1) Ω(m log m)

= 2 Ω(m² log m) + (n - m + 1) Ω(m log m)

= Ω(m n log m)

- Gareth Rees

---

这是我见过的最好的答案，点赞！看起来也是正确的，但这并不重要。 - Orbling

哇！感谢您的解释。听起来很有道理。我有几个问题不太明白：1.第二项(n-m+1)Ω(m log m)是从哪里来的？2.我想知道是否有比Ω(m² log m)更紧的Σk < m Ω(k log k)上界？ - Anil Katti

(n − m + 1) Ω(m log m) 这个式子来自矩阵从底部到顶部的对角线灰色方块：每个这样的方块包含 m 个元素，而且有 (n − m + 1) 个这样的方块。至于你的另一个问题，Ω 是一种 下界，而不是上界。 - Gareth Rees

一张好的图表胜过千言万语，可惜我不能给它10个赞来弥补 :) - Matthieu M.

@Gareth - 太好了。我明白了第二项的作用。但是，你确定Σk < m Ω(k log k)是Ω(m² log m)吗？无论如何，总和都被第二项支配，我同意这个问题的下限是Ω(m n log m)。非常感谢你提供这个精美的答案！ - Anil Katti

x log x是光滑的，因此Σk log k接近于∫x log x dx。 - Gareth Rees

Answer 2

通过创建二叉搜索树，我们可以在O(mn)时间内实现此目标。从第一列中取出最后一个元素（例如上面提到的第3个元素），将其作为根节点。右节点将是该行中大于它的n个元素，而左节点将是上面的元素，即第(m-1)个或倒数第二行的第一个元素。同样地，对于这个元素，右节点将是该行的n个元素。再次，m-2将是左元素，而其行中的所有n个元素将是右元素。类似地，向前移动，我们将在O(mn)时间内创建一个二叉搜索树。这是O(mn)，因为我们在插入时不进行搜索，只需通过移动根节点指针进行简单的插入遍历。然后对此BST进行中序遍历，这也将是O(mn)时间。

- Maggy

---

你所描述的过程确保“左节点”不会比其父节点大，“右节点”不会比其父节点小。但这并不一定构建了一个二叉搜索树——考虑第二个例子（第二列的第一个元素小于第一列的最后一个元素=根节点），或者类似地，a₁₁=1，a₁₂=2，a₂₁=3，a₂₂=4。 - greybeard

Answer 3

如果元素是在某个范围k内的整数，其中K = o(mn)，我们可以使用计数排序并使用额外空间来实现O(mn)。否则，mnlog(min(m,n))是我们能做到的最好的。

- Daniel