algorithm - Shellsort - 如果一个数组是 g-sorted 然后 h-sorted，数组仍然是 g-sorted

Question

以下是来自普林斯顿的 coursera 算法类(class)的练习。

如果一个数组既是 3 次排序又是 5 次排序，那么它是否也是 6 次、7 次、8 次、9 次和 10 次排序？我知道任何序列如果先 g-sorted 然后 h-sorted，它仍然是 g-sorted。但这如何解释这个问题呢？如果数组是 3 排序和 5 排序，它与 6 排序或 7 排序等有什么关系？提前致谢!

Answer 1

好吧，关于 6、9 和 10 排序，这些只是基本排序运行中的替代条目(例如，6 排序是 3 排序中的每隔一个条目)。所以你可以说对于一个h排序的数组，这个数组也是kh排序的，其中k是一个大于0的正整数。8排序理解起来有点棘手，但是说这个数组是8就足够了-排序，因为 8 是 3 和 5 的和。出于类似的原因，我们可以说数组不是 7 排序的，因为你不能从 5 和 3 构造 7。