任取5个数，求证：至少通过7次比较可把原数列变成有序数列
比较的同时可进行交换，如比较3和4的大小后交换3和4算一次比较
证明时请给出算法

设A={a1,a2,a3,a4,a5}
1.
第1,2次分别比较a1和a2,a3和a4
后可假设
a1<a2,a3<a4

2.
第3次比较a2和a4,
分别有
ⅰ.
a1<a2<a4,a3<a4.
ⅱ.
a3<a4<a2,a1<a2
两种相似的情况.

所以只需研究
ⅰ.a1<a2<a4,a3<a4就可以了.

4.设前3次已知:a1<a2<a4,a3<a4
第4次比较a2和a5,
分别有
ⅰ.
a2<a5.
ⅱ.
a2>a5
两种情况.

5.
若是4.的ⅰ.的情况,
即a1<a2<a4,a3<a4,a2<a5.
第5次比较a4和a5后,有
ⅰ.
a1<a2<a4<a5,a3<a4.
ⅱ.
a1<a2<a5<a4,a3<a4.

((1)) 若是ⅰ.
a1<a2<a4<a5,a3<a4.
第6,7次比较a3和a2,a1后,就可把原数列变成有序数列.

((2)) 若是ⅱ.
a1<a2<a5<a4,a3<a4.
第6次比较a3和a2后,
再根据情况,第7次比较a3和a1或a5后,
就可把原数列变成有序数列.

5.
若是4.的ⅱ.
a2>a5的情况,
即a1<a2<a4,a3<a4,a5<a2.
第5次比较a1和a5后,有
分别有
ⅰ.
a1<a5<a2<a4,a3<a4.
ⅱ.
a5<a1<a2<a4,a3<a4
两种相似的情况.

所以只需研究
ⅰ.a1<a5<a2<a4,a3<a4就可以了.

6.
设前5次已知:a1<a5<a2<a4,a3<a4.
第6次比较a3和a5后,
再根据情况,第7次比较a3和a1或a2后,
就可把原数列变成有序数列.

所以只需通过7次比较可把原数列变成有序数列.