shell排序算法比合并排序算法好吗？

Question

我和一群书呆子有一个关于算法的小演示，我被随机要求说服他们外壳排序比合并排序算法更好……我已经阅读了几乎弱的排序，但无论我读了多少关于合并排序和外壳排序的内容，我都发现合并排序比外壳排序更好。

shell排序在合并排序上有什么优势吗？我的意思是在什么情况下shell排序比合并排序更好。我可能遗漏了一些东西，但我不知道是什么。

任何提示都可以，如果可能的话，你能给我链接一些有用的东西吗？

Answer 1

你必须记住shellsort提出的背景: shellsort发表于1959年；quicksort发表于1961年；mergesort发表于1948年(好吧，这有点令人惊讶)。当时的计算机速度很慢，内存也很小。因此，与增加的实现和代码复杂性相比，合并排序的渐近优势几乎是不相关的。事实上，sort排序免费获得了现代实用合并排序的二次后备，因为间隔为1的插入排序就是插入排序。

当时还不知道如何进行有效的就地合并(即使是现在，也没有人实现它，因为它在实践中效率非常低)。

Shellsort有一个简单的非递归实现。高级语言中的递归仅限于LISP (因此不切实际，更不用说缺少数组类型)和尚未实现的ALGOL 60标准。

对于大多数已排序的数据，Shellsort的运行时间都有很大改进。(不过，它不是Timsort。)

Answer 2

合并排序通常比shell排序更快，但是shell排序已经存在。如果对数据进行排序，快速排序会更快，但如果对指向数据的指针或索引的数组进行排序，合并排序通常会更快，如果元素的比较开销大于指针或索引的移动开销，因为合并排序比快速排序使用更少的比较但更多的移动。如果对随机整数数组进行排序，那么计数/基数排序是最快的。

如前所述，merge sort于1948年发布。旧大型机上的合并排序是在磁带驱动器或磁盘驱动器上实现的。对于磁带机，有/有合并排序的变体：

http://en.wikipedia.org/wiki/Polyphase_merge_sort

http://en.wikipedia.org/wiki/Oscillating_merge_sort

自然合并排序利用了任何现有的自然排序，但有跟踪可变大小运行的开销。对于磁带驱动器，这可以/可以使用单个文件标记来表示运行结束，使用双文件标记来表示数据结束。具有可变大小块的早期磁盘驱动器可以实现类似的东西(使用小块来指示运行结束/数据结束)。

http://en.wikipedia.org/wiki/Merge_sort#Natural_merge_sort

自然合并排序的另一种选择是tim排序，其中使用插入排序的自然和/或强制排序用于在初始遍历期间创建固定大小的运行：

http://en.wikipedia.org/wiki/Timsort

“经典”归并排序是自下而上的归并排序，并且在外部排序的情况下，使用磁带驱动器或磁盘驱动器，初始遍对存储器中的数据进行排序，以跳过初始归并遍，类似于tim排序，除了存储器排序可能不是插入排序，并且通常对指针或索引的数组进行排序，并且根据这些指针或索引写入数据，而不是在写入之前对存储器中的数据进行排序。在某些系统上，使用具有多个数据指针/长度的单个I/O。SATA / IDE / SCSI PC控制器有一组描述符，用于保存地址/长度数据以处理分页内存，但我不知道是否有用于PC的高端排序程序使用这些描述符来写入一组记录，以便使用单个I/O进行合并排序。

我不确定什么时候第一次发布自顶向下的合并排序。它不是从一些固定或可变的运行大小开始，并在合并运行时使用迭代来推进索引或指针，而是递归地生成索引或指针，直到它们表示一些小的固定运行大小，通常是运行大小为1，然后才会发生任何实际的数据合并。无论由于运行合并的深度优先/左优先排序的高速缓存本地化可能存在什么优势，它都被递归的开销所抵消，并且通常自上而下的合并排序比自下而上的合并排序稍微慢一些(大约5%)。

Answer 3

这取决于您对“更好”的定义，但如果您查看一个常用的度量标准-最坏情况下的性能-合并排序(O(n log n))实际上比外壳排序(O(n^2))更快。

就空间复杂性而言，两者都可以就地实现，因此shell排序在这里也没有优势。