在 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次运行s，它将return一个负值变为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]);
   }
}

外层循环遍历数组的所有元素，表示"put each one in place."内层循环表示"keep swapping the current element with the one that comes before it as long as there is an element that comes before it and that element is greater than it."这里使用+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。内部循环当前表示 "repeatedly swap every element backwards toward the front until it comes to rest." 如果您从该循环中删除 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
        ^ ^              ^ ^

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

在 C 中实现 shellsort 算法

Implementing shellsort algorithm in C

c

sorting

algorithm

shellsort