用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...的增量。

这意味着前5次这个内部for循环运行，它将返回一个负值给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和--是因为我们经常查看紧跟在当前元素之前的元素。

在step排序中，我们在数组上运行这个算法的多次传递，只不过我们不使用一个步骤的大小。相反，我们使用一定数量的步长，称为间隙量。因此，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的数组进行array排序：

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
        ^ ^              ^ ^

正如你所看到的，现在一切都得到了正确的处理。