Understanding ShellSort code from c K&R Book at page 62

Question

我试图理解 K&R 书中第 62 页的 ShellSort 代码。但有一部分我不确定。

这里是书中的原始代码：

void shellsort(int* v, int n) {
    int gap, i, j, temp;
    for (gap = n / 2; gap > 0; gap /= 2) {
        for (i = gap; i < n; i++) {
            for (j = i - gap; j >= 0 && v[j] > v[j + gap]; j -= gap) {
                temp = v[j];
                v[j] = v[j + gap];
                v[j + gap] = temp;
            }
        }
    }
}

我正在尝试理解为什么会有第三个循环。只有在不能的情况下才可以吗？

这是代码的更改版本（我认为也可以使用的代码）：

void shellsort(int* v, int n) {
    int gap, i, j, temp;
    for (gap = n / 2; gap > 0; gap /= 2) {
        for (i = gap; i < n; i++) {
            j = i - gap;
            if (v[j] > v[j + gap]) {
                temp = v[j];
                v[j] = v[j + gap];
                v[j + gap] = temp;
            }
        }
    }
}

当我 运行 代码时，它输出与第一个代码相同的内容：

输出：

12345679

但肯定有一些使用 for 的原因。我找不到那是什么原因。所以我认为有人可以解决这个问题？

Answer 1

如果您跟踪算法的作用，您可能会更好地了解正在发生的事情。这是您的程序的一个版本，其中包含一些额外的打印语句：

void shellsort(int* v, int n) {
    int gap, i, j, temp;
    for (gap = n / 2; gap > 0; gap /= 2) {
        printf("enter outer loop with gap = %d\n", gap);
        for (i = gap; i < n; i++) {
            printf("- enter second loop with i = %d\n", i);
            for (j = i - gap; j >= 0 && v[j] > v[j + gap]; j -= gap) {
                temp = v[j];
                v[j] = v[j + gap];
                v[j + gap] = temp;
            }
            printf("- after innermost loop:");
            print_array(v, n);
        }
    }
}

（我省略了print_array的定义。）

按照评论者的建议，使用数组 { 5, 4, 3, 2, 1 } 调用它，得到以下输出：

 5 4 3 2 1
enter outer loop with gap = 2
- enter second loop with i = 2
- after innermost loop: 3 4 5 2 1
- enter second loop with i = 3
- after innermost loop: 3 2 5 4 1
- enter second loop with i = 4
- after innermost loop: 1 2 3 4 5
enter outer loop with gap = 1
- enter second loop with i = 1
- after innermost loop: 1 2 3 4 5
- enter second loop with i = 2
- after innermost loop: 1 2 3 4 5
- enter second loop with i = 3
- after innermost loop: 1 2 3 4 5
- enter second loop with i = 4
- after innermost loop: 1 2 3 4 5
 1 2 3 4 5

但是，如果我使用您的代码，仅使用 if 而不是最内层的 for 循环，会发生以下情况：

 5 4 3 2 1
enter outer loop with gap = 2
- enter second loop with i = 2
- after swap: 3 4 5 2 1
- enter second loop with i = 3
- after swap: 3 2 5 4 1
- enter second loop with i = 4
- after swap: 3 2 1 4 5
enter outer loop with gap = 1
- enter second loop with i = 1
- after swap: 2 3 1 4 5
- enter second loop with i = 2
- after swap: 2 1 3 4 5
- enter second loop with i = 3
- after swap: 2 1 3 4 5
- enter second loop with i = 4
- after swap: 2 1 3 4 5
 2 1 3 4 5

结果不正确，因为 1 没有传播到数组的开头。这是由于缺少内部循环。在原始版本中，在 gap = 2 和 i = 4 处，程序比较 5 和 1 并交换它们；然后比较 3 和 1 并交换它们，以确保这三个元素（1、3、5）的相对顺序正确。没有内部循环，第二次交换就不会完成。在使用 gap = 1 的迭代中将有机会修复此问题，但再次 1 仅与一个元素 (3) 交换，但不与 2 交换。

或者，对于更短但更晦涩的答案：Shell sort 在插入排序的变体上对各种 "gap sizes" 执行循环。如果你了解插入排序，你就会知道它由两个嵌套循环组成。如果删除最内层循环，就会破坏内部插入排序。

最后，在您刚刚运行的示例中，您只是运气不佳：如果输入（大部分）已排序，即使是损坏的排序算法似乎也可以运行。这些东西很难测试。