关于Shell排序的几个问题

Question

我是一个大二的学生，正在上数据结构课，今天的课是关于排序算法的。我们学习了选择排序、气泡排序、插入排序、Shell排序、快速排序和合并排序(类按此顺序排列)。据我所知，Shell排序是为了比普通插入排序更快而设计的。

所以程序是：

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

我希望我在此之前没有错。如果我是，请告诉我。

如果我是对的，我的问题是：

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

Answer 1

你做了一个有趣的观察。递归Shellsort思想在某种程度上已被用于OEIS序列A036569 (在维基百科文章[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]底部的图所示，这种在间隙之间有较大GCD的IS85序列，其间隙之间的GCD较小的其他序列要差。

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