sorting - 关于Shell排序的问题

Question

我是一名大二学生，正在上数据结构课，今天的课是关于排序算法的。我们学习了选择排序、冒泡排序、插入排序、Shell 排序、快速排序和归并排序（课程按此顺序）。据我所知，Shell 排序的设计和设计比普通的插入排序更快。

所以程序是：

1. 使用 gap 将原始列表分成几个子列表。
2. 使用插入排序对子列表进行排序。
3. 不断减小gap，重复直到gap达到1。

我希望我没有错直到这个级别。如果我是，请告诉我。

如果到目前为止我是对的，我的问题是：

如果这种称为“Shell 排序”的算法被设计并被认为比普通的插入排序更快，那么为什么不在步骤 2 中递归地使用 Shell 排序呢？根据这个逻辑，在对子列表进行排序时使用 Shell 排序而不是插入排序可以加快速度。

Answer 1

你做了一个有趣的观察。递归 Shellsort 的思想在某种程度上已经在 OEIS 序列中得到应用A036569（在 Wikipedia 文章 [ 1 ] 中搜索）：

1 3 7 3*7 3*16 7*16 3*7*16 3*7*41 3*16*41 7*16*41 3*7*16*41...

然而，正如 [ 1 ]底部的图所示，该IS85序列在其间隙之间具有较大的 GCD，不如在其间隙之间具有较小 GCD 的其他序列。

显然，Shellsort 将子列表交织的步骤越多，它进行的整体比较就越少（这是基于经验结果的猜想，而不是定理）。对于一个极端的例子，请阅读 [ 1 ] 中关于 Shell 的原始间隙序列的行为。