h-排序 Shell 排序

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（最大）应该小于listSize/3？

Answer 1

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

Answer 2

推荐用于Shell排序的最佳序列称为Knuth Sequence，实际上是3h+1，h从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排序，建议大家在reverseorder时按照这个顺序选择最优“差距”。为此，您必须找到小于 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;
}

h-sorting in Shell sort