阿苏尔
2016-05-11 15:08
采纳率: 100%
浏览 1.3k
已采纳

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

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

  • 写回答
  • 好问题 提建议
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • 小灸舞 2016-05-12 00: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

    评论
    解决 无用
    打赏 举报
  • 查看更多回答(1条)

相关推荐 更多相似问题