矩阵的行列排序

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

问题

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

解法

以下假设 是一个 矩阵

解法1

假设最终的矩阵中 , 那么 . 可能的 和 共计有 个, 因此在进行上下排列之前必定有两个是处于同一行的. 因此 . 这违背了第一次排序的从左到右升序.

解法2

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