姑且记录一下笔试难倒我的问题. 有的时候确实不得不感叹, 比我厉害的人太多了.

问题

将一个矩阵的每一行从左到右升序排列. 将得到的矩阵的每一列从上到下升序排列. 证明最终得到的矩阵每一行从左到右是升序的.

解法

以下假设 \(A\) 是一个 \(m \times n\) 矩阵

解法1

假设最终的矩阵中 \(a_{ij} > a_{i(j+1)}\), 那么 \(a_{uj} > a_{v(j+1)}, \forall i \le u \le m, 1 \le v \le i \). 可能的 \( a_{uj} \) 和 \( a_{v(j+1)} \) 共计有 \( m+1 \) 个, 因此在进行上下排列之前必定有两个是处于同一行的. 因此 \( a_{u_{0}j} > a_{v_{0}(j+1)} \). 这违背了第一次排序的从左到右升序.

解法2

第二次排序时, 考虑一个冒泡排序的过程. 考虑对所有的列同步的冒泡, 即每一轮操作将各列的第 \( i \) 行与第 \( i+1 \) 行的元素各自进行比较, 并进行可能的交换. 可以证明每一轮操作不改变涉及的两行的有序性. 具体而言, 考虑相邻的两列, 按照是否进行交换可以分为 4 种情况. 两列同时交换和同时不交换很自然地不改变有序性. 对于需要交换的情形, 交换后的结果总是 \( a_{ij} < a_{(i+1)j} < a_{i(j+1)} < a_{(i+1)(j+1)} \), 因此仍然保持有序.