《Algorithms in C part 1-4》p172 shellSort中的for(h=1;h<=(r-1)/9;h=h*3+1)循环是什么意思？

Question

我正在研究第 172 页上来自 Sedgewick Algorithms in C part 1-4 的 Shell 排序。

我使用size（数组的长度），而不是l和r（开始和结束）；所以我的代码是

int i,j,h;
int key;
for( h=1;h<=(size-1)/9;h=h*3+1);
for(;h>0;h/=3)
{
    for(i=h;i<size;i++)
    {
        key=num[i];
        j=i;
        while(j>=h&&key>num[j-h];j-=h)
        {
            num[j]=num[j-h];
        } 
        num[j]=key;
    }
}

这些我都知道。我读 TAOCP。我知道 1, 4, 13, … 是最好的序列（可比）。但是在这个位置，我的代码有

for(h=1;h<size;h=h*3+1);

我的问题是：他为什么要写h<(size-1)/9？

“/9”是什么意思？

Answer 1

循环：

for (h = 1; h < size; h = h * 3 + 1)
    ;

大部分时间超过数组的大小。替代循环将间隙保持在范围内。

您可以通过像这样的简单测试程序亲眼看到：

#include <stdio.h>

static inline int hs_gap9(int size)
{
    int h;
    for (h = 1; h <= (size - 1) / 9; h = h * 3 + 1)
        ;
    return h;
}

static inline int hs_gap3(int size)
{
    int h;
    for (h = 1; h < size; h = h * 3 + 1)
        ;
    return h;
}

int main(void)
{
    for (int i = 1; i < 100; i++)
        printf("Size: %3d; gap9 = %d; gap3 = %d\n", i, hs_gap9(i), hs_gap3(i));
    return 0;
}

示例输出：

Size:   1; gap9 =   1; gap3 =   1
Size:   2; gap9 =   1; gap3 =   4
Size:   3; gap9 =   1; gap3 =   4
Size:   4; gap9 =   1; gap3 =   4
Size:   5; gap9 =   1; gap3 =  13
Size:   6; gap9 =   1; gap3 =  13
Size:   7; gap9 =   1; gap3 =  13
Size:   8; gap9 =   1; gap3 =  13
Size:   9; gap9 =   1; gap3 =  13
Size:  10; gap9 =   4; gap3 =  13
Size:  11; gap9 =   4; gap3 =  13
Size:  12; gap9 =   4; gap3 =  13
Size:  13; gap9 =   4; gap3 =  13
Size:  14; gap9 =   4; gap3 =  40
Size:  15; gap9 =   4; gap3 =  40
Size:  16; gap9 =   4; gap3 =  40
…
Size:  34; gap9 =   4; gap3 =  40
Size:  35; gap9 =   4; gap3 =  40
Size:  36; gap9 =   4; gap3 =  40
Size:  37; gap9 =  13; gap3 =  40
Size:  38; gap9 =  13; gap3 =  40
Size:  39; gap9 =  13; gap3 =  40
Size:  40; gap9 =  13; gap3 =  40
Size:  41; gap9 =  13; gap3 = 121
Size:  42; gap9 =  13; gap3 = 121
Size:  43; gap9 =  13; gap3 = 121
…
Size:  97; gap9 =  13; gap3 = 121
Size:  98; gap9 =  13; gap3 = 121
Size:  99; gap9 =  13; gap3 = 121

如您所见，'gap3' 算法 returns 初始值 h 大于数组的大小。 'gap9' 算法 returns 初始值 h 小于数组的大小。这在循环上节省了一点开销（节省了外循环的一次迭代，其中中间循环在第一个循环退出而不触及内循环。

《Algorithms in C part 1-4》p172 shellSort中的for(h=1;h<=(r-1)/9;h=h*3+1)循环是什么意思？

What does the for(h=1;h<=(r-1)/9;h=h*3+1) loop mean in 《Algorithms in C part 1-4》p172 shellSort?

c

sorting

algorithm

shellsort