c - 在 C 中实现 shellsort 算法

Question

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;
            }
        }
    }
 }

在这个 shellsort() 函数中，我们有 j-=gap。假设 n = 10，差距总是 5 并且 j 从 0,1,2,3,4... 。

这意味着此内部 for 循环运行的前 5 次，它将向 j 返回一个负值(例如 0-5=-5)，因此由于 j 不会大于或等于 0，它只会运行一次。

之所以可行，是因为这正是我们想要的。我们不想多次交换，因为如果我们这样做，我们只会再次交换相同的两个值，从而导致不必要的冗余。

所以，我在想为什么我们不能从循环中省略 j-=gap 因为它似乎根本不会影响功能。包含j-=gap有什么特殊原因吗？

我是不是漏掉了什么？

Answer 1

查看插入排序作为引用可能有助于了解它的来源。在插入排序中，我们从左到右扫描，向后交换每个元素，直到它大于它之前的元素(或者它回到数组的开头)。该算法的伪代码如下所示:

for (int i = 1; i < n; i++) {
   for (int j = i - 1; j > 0 && A[j + 1] > A[j]; j--) {
      swap(A[j], A[j - 1]);
   }
}

外层循环遍历数组的所有元素，表示“将每个元素放在适当的位置”。内部循环表示“只要有一个元素出现在它之前并且该元素大于它，就继续将当前元素与它之前出现的元素交换。”在这里，使用 +1、++、-1 和 -- 是因为我们一直在查看紧接在当前元素之前的元素。

在 shellsort 中，我们在数组上多次运行该算法，只是我们不使用步长大小为 1。相反，我们使用一些称为间隙量的步长。因此，Shellsort 看起来像这样:

for (each gap size) {
   for (int i = gap; i < n; i += gap) {
      for (int j = i - gap; j > 0 && A[j + gap] > A[j]; j -= gap) {
         swap(A[j], A[j - 1]);
      }
   }
}

想法是每个元素都应该与它之前的 gap 元素连续比较。如果它小于这个数字，我们想将它与前面的元素交换，但又需要将它与前面的新元素反复比较。

举个例子，假设我们正在对这个长度为 6 的数组进行 shellsorting:

6 5 4 3 2 1

在第一遍 shellsort (gap = 3) 之后，数组如下所示:

3 2 1 6 5 4

现在，假设我们使用 gap = 1 执行第二遍 shellsort。内部循环目前说“反复将每个元素向后向前交换，直到它停止为止。”如果您从该循环中删除 j -= gap 步骤，那么每个元素都会直接与它之前的元素进行比较。这将导致以下结果。在这些快照中的每一个中，克拉指的是掉期的位置:

3 2 1 6 5 4   ->   2 3 1 6 5 4
^ ^

2 3 1 6 5 4   ->   2 1 3 6 5 4
  ^ ^

2 1 3 6 5 4
    ^ ^

2 1 3 6 5 4   ->   2 1 3 5 6 4
      ^ ^

2 1 3 5 6 4   ->   2 1 3 5 4 6
        ^ ^

请注意，生成的数组未排序。但是，如果我们将 j -= gap 代码放回混合中，则会发生以下情况:

3 2 1 6 5 4   ->   2 3 1 6 5 4
^ ^

2 3 1 6 5 4   ->   2 1 3 6 5 4   ->   1 2 3 6 5 4
  ^ ^              ^ ^

1 2 3 6 5 4
    ^ ^

1 2 3 6 5 4   ->   1 2 3 5 6 4
      ^ ^

1 2 3 5 6 4   ->   1 2 3 5 4 6   ->   1 2 3 4 5 6
        ^ ^              ^ ^

如您所见，现在所有内容都已正确排序。