最少比较排序问题中S(15)和S(19)的解决

• 作者: 刘晓光 刘璟 成维一 王刚
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 最少比较排序 最优排序 线性扩展计数
• 年，卷（期）: 2007,（3）
• 所属期刊栏目: 学术研究
• 页码范围: 305-313
• 页数: 9页
• 分类号: TP301.6
• 字数: 5974字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.2007.03.006

摘要

最少比较排序问题就是要研究在最坏情况下,对n个元素完成排序所需要的最少比较次数S(n).1965年M.Wells用穷举法证明了S(12)=30.2002年和2004年,M.Peczarski通过计算先后得到S(13)=34,S(14)=38,S(22)=71.文章在Wells算法和Peczarski算法基础上,设计了一个新的PS算法,并改进了线性扩展计数算法,在并行机"南开之星"上计算得到S(15)=42,S(19)=58.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王刚	南开大学信息技术科学学院	64	284	8.0	12.0
2	刘璟	南开大学信息技术科学学院	66	387	11.0	15.0
3	刘晓光	南开大学信息技术科学学院	42	135	6.0	8.0
4	成维一	南开大学信息技术科学学院	1	0	0.0	0.0