“‘Rare”排序算法？

Question

我们的算法教授给了我们一个作业，要求我们选择一个稀有的排序算法(例如Intro排序，Gnomesort，等等)。对此做些研究。维基百科确实有很多关于这方面的信息，但对我来说，深入研究还不够。因此，我想找一本书，其中包括对这些罕见排序算法的讨论，因为大多数教科书(比如我正在使用的CLRS )只讨论一些基本的排序算法(例如，Bubble排序、合并排序、插入排序)。是否有一本包含大量这些信息的书或网站？谢谢!

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

这里是维基百科链接和关于光滑排序的一篇非常广泛的文章 (基思·施瓦兹)。

Answer 2

双离子排序是O(N ^2(N))(比quicksort这样的排序稍微慢一些)，但是它是可并行的，具有高度规则的结构。这让您可以使用SIMD矢量指令集，比如SSE --提供一个恒定因子的提升，这使它成为“底层”排序的有趣选项(而不是更常用的插入排序)。

Answer 3

一种排序，你可以说是罕见的排序，是时标排序，它工作在数组的排序部分，最好的情况是O( n)，最坏的和平均的情况是O(n log N)。

另一种快速排序方法是双离子排序，它是几乎所有并行排序算法的基础。你可以在网上找到数千篇关于它的论文，还有一些像Quinn并行算法这样的书，你可以找到关于它的扩展讨论，以及这个算法的相关变体。

另外，计算机程序设计艺术第3卷对排序策略也有很好的讨论。