最少比較排序問(wèn)題研究.pdf

1、最少比較排序問(wèn)題就是要研究足以將n個(gè)元素排序所需要的最少比較次數(shù)S(n)，這是排序理論的一個(gè)基礎(chǔ)性問(wèn)題。Steinhaus在他的《MathematicalSnapshots》一書(shū)中提出最少比較排序問(wèn)題，D.Knuth在他的《TheArtofComputerProgramming》第三卷中專門(mén)用一節(jié)討論這個(gè)問(wèn)題，他在習(xí)題中給了計(jì)算S(14)一個(gè)49分的高分。 雖然比較次數(shù)不是衡量排序方法有效性的唯一方式，但是，仔細(xì)地研究比較次數(shù)會(huì)

2、給我們帶來(lái)大量的洞察排序過(guò)程本性的有用知識(shí)。自從1965年MarkWells用窮舉法證明S(12)=30以來(lái)，很少見(jiàn)到關(guān)于最少比較排序問(wèn)題的文章。Knuth在他的巨著《TheArtofComputerProgramming》中做了大量的推理，并猜測(cè)S(13)=33。2002年和2004年，M.Peczarski發(fā)表文章，介紹了他計(jì)算S(13)和S(14)、S(22)的算法，并給出計(jì)算結(jié)果S(13)=34、S(14)=38和S(22)=7

3、1。本文通過(guò)改進(jìn)M.Peczarski的算法，設(shè)計(jì)新的算法ReWM，重新計(jì)算S(13)、S(14)和S(22)，證明M.Peczarski算法的正確性，并證明通過(guò)改進(jìn)，算法的效率得到很大提高。通過(guò)對(duì)M.Wells算法、M.Peczarski算法和ReWM算法進(jìn)行并行化，計(jì)算出S(15)=42和S(19)=58。 線性擴(kuò)展計(jì)數(shù)(Countinglinearextensions)算法是計(jì)算S(n)的基礎(chǔ)算法，在Wells算法中，線性