<分区>
我们的算法教授给了我们一个作业，要求我们选择一种稀有排序算法(例如 Introsort、Gnomesort 等)并对其进行一些研究。 维基百科当然有很多关于这方面的信息，但仍然不足以让我深入研究。 所以我想找一本讨论那些稀有排序算法的书，因为大多数教科书(比如我正在使用的 CLRS)只讨论一些基本的排序算法(例如冒泡排序、归并排序、插入排序。 ). 是否有包含大量这些信息的书籍或网站？ 谢谢!
<分区>
我们的算法教授给了我们一个作业，要求我们选择一种稀有排序算法(例如 Introsort、Gnomesort 等)并对其进行一些研究。 维基百科当然有很多关于这方面的信息，但仍然不足以让我深入研究。 所以我想找一本讨论那些稀有排序算法的书，因为大多数教科书(比如我正在使用的 CLRS)只讨论一些基本的排序算法(例如冒泡排序、归并排序、插入排序。 ). 是否有包含大量这些信息的书籍或网站？ 谢谢!
最佳答案
好吧，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
这里是 wikipedia link和 a very extensive article about smoothsort (作者:基思·施瓦茨)。
关于algorithm - “稀有”排序算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8096437/