4

我试图理解第 62 页 K&R 书中的 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在那里使用。我找不到那是什么原因。所以我想有人可以清除这个吗？

4

1 回答 1

2

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

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

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

于 2016-12-25T10:59:54.613 回答