Shellsort -如果一个数组是g排序的，那么h排序的数组仍然是g排序的

Question

以下是来自普林斯顿coursera算法课程的练习。

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

Answer 1

那么，对于6、9和10排序，这些只是基本排序运行中的备用条目(例如，6排序是3排序中的每隔一个条目)。因此可以说，对于h排序的数组，该数组也是kh排序的，其中k是大于0的正整数。8排序比较难理解，但可以说数组是8排序的，因为8是3和5的和。出于类似的原因，我们可以说数组不是7排序的，因为你不能从5和3构造7。

Answer 2

数组分为3-排序和5-排序。

任何3或5的多个k (对于ex - k=6,9,10,15等)，我们肯定会排序k。

而不是3+5的和h或它们的任何倍数和(例如，h=8(3+5),11(5+6),13(10+3),16(10+6))将保持h排序的。

任何不属于上述类别的排序k-序列都不能构造，因此它们不是排序k-(ex k=7)。

Answer 3

它是6，8，9，10排序的，但不是7排序的。

因此，g排序和k排序给出(g+k)-sorted (g和k肯定是相等的)。

因此，3-排序和5-排序得到6，8，9，10-排序。(6=3+3,8=3+5,9=3+3+3,10=5+5)但是我们没有7-排序，例如：

4,1,0,5,2,7,6,3是3-排序(4，5，6，1，2，3，0，7)和5-排序(4，7，1，6，0，3)，但不是7-排序(4，3)。