加载中…将5个数的序列排序，不论原先的顺序如何，最少都可以...
(2016-09-22 15:32:33)
标签：
竞赛排序数论 |
分类： 竞赛 |
(NOIP2006普及组)将5个数的序列排序，不论原先的顺序如何，最少都可以通过（
）次比较，完成从小到大的排序。
A. 6 B. 7 C. 8 D.
9
方法一：（http://tieba.baidu.com/p/4071322403）
5个数，a、b、c、d、e
第一次比较a、b，不妨设a＞b
第二次比较c、d，不妨设c＞d
第三次比较a、c，不妨设a＞c
这个时候有结果a＞b且a＞c＞d
关键的时候到了，千万不要让b提前排序，这样会浪费掉1次。
第四次比较c，e
第五次（e＞c，则e与a比较；e＜c，则e与d比较）
第五次结束后会形成以下四种情况之一：（另已知a＞b）
1、e＞a＞c＞d
2、a＞e＞c＞d
3、a＞c＞e＞d
4、a＞c＞d＞e
情况1、e＞a＞c＞d
第六七次用b分别与c，d比较就行。
情况2、a＞e＞c＞d
第六次，b与c比较
第七次（b＞c，则b与e比较；b＜c，则b与d比较）
情况3、a＞c＞e＞d（方法同情况2继续六七次）
情况4、a＞c＞d＞e（方法同情况2继续六七次）
第一次比较a、b，不妨设a＞b
第二次比较c、d，不妨设c＞d
第三次比较a、c，不妨设a＞c
这个时候有结果a＞b且a＞c＞d
关键的时候到了，千万不要让b提前排序，这样会浪费掉1次。
第四次比较c，e
第五次（e＞c，则e与a比较；e＜c，则e与d比较）
第五次结束后会形成以下四种情况之一：（另已知a＞b）
1、e＞a＞c＞d
2、a＞e＞c＞d
3、a＞c＞e＞d
4、a＞c＞d＞e
情况1、e＞a＞c＞d
第六七次用b分别与c，d比较就行。
情况2、a＞e＞c＞d
第六次，b与c比较
第七次（b＞c，则b与e比较；b＜c，则b与d比较）
情况3、a＞c＞e＞d（方法同情况2继续六七次）
情况4、a＞c＞d＞e（方法同情况2继续六七次）
方法二：（http://bbs.csdn.net/topics/40399878）
例证法只能证明“可以”用7次比较完成，不能证明“至少”。
5个元素的全排列为5!=120，每次比较都可以把这些排列均分为二，则6次比较可以把排列分为2^6=64组。因此必然至少有两个不同排列分在同一组，而这两个排列顺序不同，无法用同一交换序列完成排序。因此，无法用小于7次的比较次数完成排序。
5个元素的全排列为5!=120，每次比较都可以把这些排列均分为二，则6次比较可以把排列分为2^6=
喜欢
0
赠金笔