理解c K&R书中的ShellSort代码(第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

如果您跟踪算法所做的事情，您可能会对所发生的事情有更好的感觉。下面是您的程序的一个版本，其中包含一些额外的print语句：

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排序在插入排序的变体上执行不同“间隙大小”的循环。如果知道插入排序，就知道它由两个嵌套循环组成。如果删除最内部的循环，则会破坏内部插入排序。

最后，在刚刚成功的示例中，您只是运气不佳:如果输入(大部分)是排序的，那么即使是损坏的排序算法也可能工作。这些东西很难检验。