'稀有'排序算法？

Question

我们的算法教授为我们提供了一项任务,要求我们选择一种罕见的排序算法(例如Introsort,Gnomesort等)并对其进行一些研究.维基百科肯定有很多关于此的信息,但我仍然不足以进行深入的研究.因此,我想找到一本书,其中包括对那些罕见的排序算法的讨论,因为大多数教科书(如CLRS,我正在使用的)只讨论了一些基本的排序算法(例如冒泡排序,合并排序,插入排序). ).是否有包含大量这些信息的书籍或网站？谢谢!

Answer 1

嗯,Edsger Dijkstra在Smoothsort中一个非常有趣的"罕见"排序算法.在纸面上它几乎是一个完美的类型:

O(n) best
O(n log n) average
O(n log n) worst
O(1) memory

n comparisons, 0 swaps when input is sorted

它是如此罕见,因为它的复杂性(这使得它很难优化).

你可以在这里阅读Dijkstra自己撰写的论文:http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF

这里是维基百科链接和关于smoothsort的非常广泛的文章(由Keith Schwarz提供).