在C语言中实现希尔排序算法

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？

我在这里漏掉了什么吗？

- jimo

---

最终，“gap”缩小到“1”。您需要多次重复内部循环。 - Jonathan Leffler

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 和-- 的使用是因为我们一直在查看当前元素之前紧挨着的那个元素。

在希尔排序中，我们对数组运行多次此算法，但步长不是1，而是某个被称为间隔量的数量。因此，希尔排序看起来像这样:

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的数组进行希尔排序：

6 5 4 3 2 1

在希尔排序（gap = 3）的第一轮之后，数组看起来像这样：

3 2 1 6 5 4

现在，想象一下我们使用gap = 1进行希尔排序的第二次遍历。内循环当前说的是“反复将每个元素向前交换直到它停止”。如果从该循环中删除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
        ^ ^              ^ ^

如您所见，现在所有内容都可以得到正确排序。

- templatetypedef