例子（这里由于版面原因，只列出3*3的数组）
4 2 5 2 4 5 2 4 5
9 8 10 ->排序行 8 9 10 ->排序列 3 4 5 -> 可以发现每行还是按照从小到大排序的。
3 4 5 3 4 5 8 9 10
6 个解决方案
#1
当然是
#2
假设数组看成二维矩阵，则：
a11,a12,a13,……a1n;
a21,a22,a23,……a2n;
…………………………
…………………………
an1,an2,an3,……ann;
则先按行排列后每行都为有序的，再按列排列，则每列的最小元素上升到第一行，
比方说我没考虑行已经排好的一，二列，显然第一列的最小元素<=a'11,(a'11
为排列好的矩阵的第一个元素，且a'11<=a'12;
再将第二列元素排列，由于第二列的数在最初都要比相应的第一列的数要大，所以
第而列的最小元素肯定要>=第一列的最小元素，比方说第一列的最小元素是ar1(
对应原来的矩阵），第二列最小的数十ak2,则如果k=r,则ar2>=ar1,得证，
如果k!=r,则ak2>=ak1>=ar1,也得证，……这样也就可以证明命题的正确性．
a11,a12,a13,……a1n;
a21,a22,a23,……a2n;
…………………………
…………………………
an1,an2,an3,……ann;
则先按行排列后每行都为有序的，再按列排列，则每列的最小元素上升到第一行，
比方说我没考虑行已经排好的一，二列，显然第一列的最小元素<=a'11,(a'11
为排列好的矩阵的第一个元素，且a'11<=a'12;
再将第二列元素排列，由于第二列的数在最初都要比相应的第一列的数要大，所以
第而列的最小元素肯定要>=第一列的最小元素，比方说第一列的最小元素是ar1(
对应原来的矩阵），第二列最小的数十ak2,则如果k=r,则ar2>=ar1,得证，
如果k!=r,则ak2>=ak1>=ar1,也得证，……这样也就可以证明命题的正确性．
#3
每行的元素还是从小到大排序的
#4
变换之后的矩阵每行中的元素还是从小到大排列的。证明如下：
用反证法，假设存在一处a[i, j] > a[i, j+1]。
因为列中元素是经过排序的，所以必定有：
a[1, j+1] <= a[2, j+1] <= …… <= a[i, j+1] < a[i, j]
也就是说，第j+1列中存在着 i 个比a[i, j]还要小的元素。
这就是说，在 行排序之后 列排序之前，在原来的第 j 列中一定还有至少 i 个比a[i, j]还要小的数字（其实就是与a[1, j+1] ，a[2, j+1] ， …… a[i, j+1]同行的这 i 个 ，它们比a[1, j+1] ，a[2, j+1] ， …… a[i, j+1]还要小，当然更比a[i, j]小）。
这说明，如果对第 j 列排序的话，a[i, j]这个元素排不到第 i 行(因为同列中至少有i个元素是比它还要小的)，这与[i, j]的下标明显是矛盾的。
从而假设不成立。
不知道说清楚了没，反正我看着是挺明白的：）
用反证法，假设存在一处a[i, j] > a[i, j+1]。
因为列中元素是经过排序的，所以必定有：
a[1, j+1] <= a[2, j+1] <= …… <= a[i, j+1] < a[i, j]
也就是说，第j+1列中存在着 i 个比a[i, j]还要小的元素。
这就是说，在 行排序之后 列排序之前，在原来的第 j 列中一定还有至少 i 个比a[i, j]还要小的数字（其实就是与a[1, j+1] ，a[2, j+1] ， …… a[i, j+1]同行的这 i 个 ，它们比a[1, j+1] ，a[2, j+1] ， …… a[i, j+1]还要小，当然更比a[i, j]小）。
这说明，如果对第 j 列排序的话，a[i, j]这个元素排不到第 i 行(因为同列中至少有i个元素是比它还要小的)，这与[i, j]的下标明显是矛盾的。
从而假设不成立。
不知道说清楚了没，反正我看着是挺明白的：）
#5
-dlym, 你的反证法是正确的，也很明白，谢谢。
-lyg_wangyushi，不好意思，没看懂你的意思。
这个题目能给出正面的证明吗？
-lyg_wangyushi，不好意思，没看懂你的意思。
这个题目能给出正面的证明吗？
#6
每次操作都使得结果成立，那么最后的结果必然成立阿
#1
当然是
#2
假设数组看成二维矩阵，则：
a11,a12,a13,……a1n;
a21,a22,a23,……a2n;
…………………………
…………………………
an1,an2,an3,……ann;
则先按行排列后每行都为有序的，再按列排列，则每列的最小元素上升到第一行，
比方说我没考虑行已经排好的一，二列，显然第一列的最小元素<=a'11,(a'11
为排列好的矩阵的第一个元素，且a'11<=a'12;
再将第二列元素排列，由于第二列的数在最初都要比相应的第一列的数要大，所以
第而列的最小元素肯定要>=第一列的最小元素，比方说第一列的最小元素是ar1(
对应原来的矩阵），第二列最小的数十ak2,则如果k=r,则ar2>=ar1,得证，
如果k!=r,则ak2>=ak1>=ar1,也得证，……这样也就可以证明命题的正确性．
a11,a12,a13,……a1n;
a21,a22,a23,……a2n;
…………………………
…………………………
an1,an2,an3,……ann;
则先按行排列后每行都为有序的，再按列排列，则每列的最小元素上升到第一行，
比方说我没考虑行已经排好的一，二列，显然第一列的最小元素<=a'11,(a'11
为排列好的矩阵的第一个元素，且a'11<=a'12;
再将第二列元素排列，由于第二列的数在最初都要比相应的第一列的数要大，所以
第而列的最小元素肯定要>=第一列的最小元素，比方说第一列的最小元素是ar1(
对应原来的矩阵），第二列最小的数十ak2,则如果k=r,则ar2>=ar1,得证，
如果k!=r,则ak2>=ak1>=ar1,也得证，……这样也就可以证明命题的正确性．
#3
每行的元素还是从小到大排序的
#4
变换之后的矩阵每行中的元素还是从小到大排列的。证明如下：
用反证法，假设存在一处a[i, j] > a[i, j+1]。
因为列中元素是经过排序的，所以必定有：
a[1, j+1] <= a[2, j+1] <= …… <= a[i, j+1] < a[i, j]
也就是说，第j+1列中存在着 i 个比a[i, j]还要小的元素。
这就是说，在 行排序之后 列排序之前，在原来的第 j 列中一定还有至少 i 个比a[i, j]还要小的数字（其实就是与a[1, j+1] ，a[2, j+1] ， …… a[i, j+1]同行的这 i 个 ，它们比a[1, j+1] ，a[2, j+1] ， …… a[i, j+1]还要小，当然更比a[i, j]小）。
这说明，如果对第 j 列排序的话，a[i, j]这个元素排不到第 i 行(因为同列中至少有i个元素是比它还要小的)，这与[i, j]的下标明显是矛盾的。
从而假设不成立。
不知道说清楚了没，反正我看着是挺明白的：）
用反证法，假设存在一处a[i, j] > a[i, j+1]。
因为列中元素是经过排序的，所以必定有：
a[1, j+1] <= a[2, j+1] <= …… <= a[i, j+1] < a[i, j]
也就是说，第j+1列中存在着 i 个比a[i, j]还要小的元素。
这就是说，在 行排序之后 列排序之前，在原来的第 j 列中一定还有至少 i 个比a[i, j]还要小的数字（其实就是与a[1, j+1] ，a[2, j+1] ， …… a[i, j+1]同行的这 i 个 ，它们比a[1, j+1] ，a[2, j+1] ， …… a[i, j+1]还要小，当然更比a[i, j]小）。
这说明，如果对第 j 列排序的话，a[i, j]这个元素排不到第 i 行(因为同列中至少有i个元素是比它还要小的)，这与[i, j]的下标明显是矛盾的。
从而假设不成立。
不知道说清楚了没，反正我看着是挺明白的：）
#5
-dlym, 你的反证法是正确的，也很明白，谢谢。
-lyg_wangyushi，不好意思，没看懂你的意思。
这个题目能给出正面的证明吗？
-lyg_wangyushi，不好意思，没看懂你的意思。
这个题目能给出正面的证明吗？
#6
每次操作都使得结果成立，那么最后的结果必然成立阿