2.5.30

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

不妨按照升序排序,$ x_{ij} $ 代表第 $ i $ 行第 $ j $ 列的元素。

首先保证每列都是有序的。
对第一行排序,对于第一行的元素 $ x_{1i} $ ,排序结果无非两种。
要么 $ x_{1i} $ 不改变,要么和更小的元素进行交换。
显然,无论哪种情况,第 $ i $ 列都是有序的。
因此对第一行排序之后,第一行有序,每一列都分别有序。

之后我们对第二行排序,考虑元素 $ x_{11} $。
此时 $ x_{11} $ 小于第一列的所有其他元素,也小于第一行的所有其他元素。
又每一列都分别有序,因此 $ x_{11} $ 是整个矩阵的最小值,第二行不存在比它小的元素。
考虑使用选择排序,我们把第二行的最小值和 $ x_{21} $ 交换,第一列仍然有序。
现在去掉第一列,对剩下的矩阵做一样的操作,可以将第二行依次排序。
同时保证第二行的元素都小于同列的第一行元素。

接下来的行都可以依次类推,最终将整个矩阵的所有行排序,定理得证。

上一题 下一题