问Shell排序中的h-排序

EN

如果在条件h之后继续增加(h < listSize/3)，h就会比listSize大，而h排序没有意义--我们不能比较条目A[i]和A[i+h]，因为第二个索引超出了列表范围。

为Shell排序推荐的最优序列称为Knuth序列，它实际上是从0开始h的3h+1，并被前面方程的解所代替。

h=0;    3*0+1=1
h=1;    3*1+1=4
h=4;    3*4+1=13
h=13;   3*13+1=40 and so on.

现在，对于Shell排序，建议您在选择最佳“间隙”时按照反向 order中的顺序进行操作。要做到这一点，您必须找到最后一个“差距”，它比listsize小。

假设您的列表大小为n=100，那么您希望空白为40,13,4,1

int gap;
for(int h=0; h<n; h=h*3+1)
    gap=h;

这会让你活到40岁现在执行插入排序，从技术上以gap=gap/3的形式得到以前的gap值，但是由于其余部分被丢弃，所以我们不担心它。

所以你得到了最后的代码，比如：

for(int h=0; h<n; h=h*3+1)
    gap=h;

while(gap>=1)
{
    //insertion sort with gap increments
    gap=gap/3;
}