2 u010132497 u010132497 于 2016.05.11 23:08 提问

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

#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是用来干嘛的?,为什么要这么做?我是新手,希望大家帮帮忙

3个回答

qq423399099
qq423399099   Ds   Rxr 2016.05.12 08:50
已采纳

希尔排序是对每组记录采用直接插入排序方法进行排序
当你第一趟的时候,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

qq423399099
qq423399099 回复阿苏尔: 对
一年多之前 回复
u010132497
u010132497 j -=gap实现了把小的数往前移gap个距离。以gap=3为例,下标为0,3,6,9,12.假设下标12时数最小,那么第一次当i移动到下标12时,12和9比较,小的数给9,然后9和6比较,小的数给6,这样依次类推,最终0位为最小的数。是这样吧?
一年多之前 回复
CSDNXIAON
CSDNXIAON   2016.05.11 23:12

TSP问题,求帮忙。
求大虾帮忙解答个C语言编程
没解决的问题,如果你看到了请帮忙解答下好吗?
----------------------同志你好,我是CSDN问答机器人小N,奉组织之命为你提供参考答案,编程尚未成功,同志仍需努力!

u010132497
u010132497   2016.05.11 23:11

对不起,注释代码中数组下标全部改成j+gap

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!