最少比较排序问题的新结果

摘要：

最少比较排序问题就是要研究在最坏情况下,对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算法.通过对Wells算法、Peczarski算法、PS算法进行并行化,利用巨型机”南开之星”计算出S(15)=42,S(19)=58.

关键词： 最优排序 最少比较排序 线性扩展计数

作者: 成维一 刘晓光 王刚 刘璟

作者单位: 南开大学信息技术科学学院,天津,300071

会议类型: 国内会议

会议名称: 2006年全国高性能计算学术会议(HPC 2006)

会议地点: 北京

会议语种:中文

在线出版日期: 2006-10-27（万方平台首次上网日期，不代表论文的发表时间）