欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

5个数排列所需的最少比较次数

程序员文章站 2024-01-17 14:37:10
...

转:http://blog.csdn.net/fisher_jiang/article/details/2442486

5 个数最快的排序, H.B.Demuth 于 1956 年在他的博士论文中提出了以下方法:

开始时,就像用合并对4个元素排序一样,首先比较a:b,接着 c:d,然后把每对的较大者拿来比较,这就产生了a<b<d和 c<d, 进行 3 次比较, 可以找到如下有序关系 (以下图中所有连线均表示左下元素比右上元素小)
 b--d
 /    /
a c e

 

这时,我们把第5个元素e,插入到{a,b,d}当中的适当位置,只需比较两次,首先同b进行比较,而后同a或d进行比较,就有如图所示的四种情况
    b-d   e-b-d    b-e-d    b-d-e
    /  /        /   /      /    /       /  /
e-a c     a  c     a   c     a c
对以上任意一种情况, 总可以通过两次比较将 c 调整入由 abde 构成的有序队中 (用二分的思想)
这样处理后总共需要比较 3 + 2 + 2 = 7 次, 能选出答案 7 并且解答过程无误的可以给双倍的分
资料来源: [Ph.D.thesis, Standford University(1956), 41~43]
同时在 D.E.Knuth 的著作 <计算机程序设计艺术> (The Art of Computer Progamming) 第三卷(排序和查找) 173 页至 174 页对这个问题有一个详细的解释.

相关标签: c