在矩阵中执行以下步骤:1.对每列中的每个数据进行排序;2.对每行中的每个数据进行排序;
证明每列中的数据仍然是有序的。我不知道如何证明这一点。
这里我们将看到一个矩阵,它已经进行了列排序。我们将展示,行排序完成后,每个元素将不小于其下方的元素。
设x
为最上面一行中某项的值。
设n
是顶行中大于或等于x
的元素的数目。
x
必须在矩阵的左n
点中。
这意味着,在下面的行中至少有不小于x
的n
元素,这是因为在顶行中不小于x
的每个n
元素在它们下面都有不小于的东西。
这意味着,在x
之下存在一个大于x
的元素。
通过归纳法,我们可以将其应用于每一行。