希尔排序问题，求帮忙解答

Question

#include

#define NUM 15
void shellsort(int [], int);

int main()
{
int i = 0;

int v[NUM] = {3,1,4,5,2,8,6,7,9,12,15,23,21,15,10};
shellsort(v,NUM);
for(i = 0; i < NUM; i++)
    printf("%d\n",v[i]);
return 0;

}
//希尔排序
void shellsort(int v[], int n)
{
int gap; //元素距离
int i, j, temp = 0;

for(gap = n/2;gap > 0; gap /= 2)//控制两个被比较元素的距离，从n/2开始，逐步进行对折，知道距离为0
    for(i = gap; i < n; i++)    //用于在元素间移动位置
      for(j = i - gap; j >=0 && v[j] > v[j+gap]; j -= gap) //比较各对相距gap个位置的元素，逆序时交换
        {
            temp = v[j+gap];
            v[j+gap] = v[j];
            v[j] = temp;
        }

}

问题在于，我不明白原书中，第三个嵌套for中，j-=gap是用来干嘛的？，为什么要这么做？我是新手，希望大家帮帮忙

Answer 1

希尔排序是对每组记录采用直接插入排序方法进行排序
当你第一趟的时候，gap=7,等于是分了7个组进行比较，最后一组只有一个元素
第二趟的时候，gap=3,等于是分成3个组比较,第一组是下标为0,3,6,9,12,第二组是(1,4,7,10,13),第三组是(2,5,8,11,14)
第三趟的时候,gap=1,只剩一组了
因为每趟比较都是分组比较的，而当前这趟同一组里的元素下标相距gap的长度，所以需要j-=gap
看看这个，有图方便理解一点：http://www.cnblogs.com/jingmoxukong/p/4303279.html