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开始递增。这意味着这个内部循环运行的前5次，它将返回一个负值到
j（例如0,1,2,3,4...），因此由于for不会大于或等于j，它将只运行一次。它起作用是因为那正是我们想要的。我们不想交换不止一次，因为如果交换了，我们只会再次交换相同的两个值，从而导致不必要的冗余。
所以，我在想为什么我们不能忽略循环中的
0-5=-5，因为它似乎根本不会影响功能。包含j有什么特殊原因吗？我是不是丢了什么东西？
最佳答案
把insertion sort作为一个引用来查看它的来源可能会有所帮助。在插入排序中，我们从左到右扫描，向后交换每个元素，直到它大于它前面的元素（或者它回到数组的开头）。该算法的伪代码如下所示：
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]);
}
}
}
其思想是每个元素都应该与之前的元素进行连续比较。如果小于该数字，我们希望将其与前面的元素交换，但随后需要重复将其与前面的新元素进行比较。
例如，假设我们对这个长度为6的数组进行外壳排序：
6 5 4 3 2 1
在shellsort（
gap）的第一次传递之后，数组如下所示：3 2 1 6 5 4
现在，假设我们使用
gap = 3执行shellsort的第二步。内部循环现在说“重复地将每个元素向后交换到前面，直到它停止。”如果从该循环中删除gap = 1步骤，那么每个元素只会与它前面的元素进行比较。这将导致以下结果。在每一张快照中，克拉指的是掉期的目标：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代码放回mix中，则会发生以下情况：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
^ ^ ^ ^
如你所见，现在一切都得到了正确的排序。