c - Shell排序中的h排序

Question

在 shell 排序中，3h+1建议使用插入排序对列表进行 h 排序

//1, 4, 13, 40, ...

计算起始值的最佳公式h是的三分之一listsize，如下所示，

int h = 1;
while(h < listSize/3){ // why N/3?

  h = 3*h + 1
}
while(h >= 1){

  //h-sort the array
  // perform insertionSort
  h = h/3;
}

问题：

要执行 shell 排序，如何在数学上证明h(at max) 应该小于listSize/3？

score 3 · Accepted Answer

h如果我们在 condition 之后继续增加(h < listSize/3)，h变得大于listSize，并且在 h 排序中没有意义 - 我们无法比较项目A[i]，A[i+h]因为第二个索引超出了列表范围。

score 1 · Accepted Answer

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

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 排序，建议您在选择最佳“间隙”时以相反的 顺序遵循此顺序。为此，您必须找到小于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=(gap-1)/3但是由于剩余部分被丢弃，因此我们不必担心。

所以你得到了类似的最终代码：

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

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

2 回答 2