论文部分内容阅读
最少比较排序问题就是要研究足以将n个元素排序所需要的最少比较次数S(n)，这是排序理论的一个基础性问题。Steinhaus在他的《MathematicalSnapshots》一书中提出最少比较排序问题，D.Knuth在他的《TheArtofComputerProgramming》第三卷中专门用一节讨论这个问题，他在习题中给了计算S(14)一个49分的高分。
虽然比较次数不是衡量排序方法有效性的唯一方式，但是，仔细地研究比较次数会给我们带来大量的洞察排序过程本性的有用知识。自从1965年MarkWells用穷举法证明S(12)=30以来，很少见到关于最少比较排序问题的文章。Knuth在他的巨著《TheArtofComputerProgramming》中做了大量的推理，并猜测S(13)=33。2002年和2004年，M.Peczarski发表文章，介绍了他计算S(13)和S(14)、S(22)的算法，并给出计算结果S(13)=34、S(14)=38和S(22)=71。本文通过改进M.Peczarski的算法，设计新的算法ReWM，重新计算S(13)、S(14)和S(22)，证明M.Peczarski算法的正确性，并证明通过改进，算法的效率得到很大提高。通过对M.Wells算法、M.Peczarski算法和ReWM算法进行并行化，计算出S(15)=42和S(19)=58。
线性扩展计数(Countinglinearextensions)算法是计算S(n)的基础算法，在Wells算法中，线性扩展计数占用了约70％的时间，本文对线性扩展计数算法进行了改进。得益于这种改进，我们计算出S(19)=58，实验证明，新算法极大的提高了线性扩展计数的效率。