关于D.L.Shell 排序算法的问题

bsdwiki

这是K&R上的关于shell排序的例程：

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;
                   }
}

其余的都看明白了，唯独标红的第三层循环实在是看不懂，请前辈们百忙之中讲解一下，多谢了

[ 本帖最后由 bsdwiki 于 2009-5-28 17:10 编辑 ]

daybreakcx

这个过程是错的吧，你打错变量了吧，实验得到的值不对

bsdwiki

不好意思，已经修改过来了，第三层循环应该是：

for (j= i-gap;j >= 0 && v[j] > v[j+gap]; j -= gap)

daybreakcx

是这样的，其实最内部的那层循环是一个插入排序的过程，假设当前i定下来，那么就能够得到一个以v [ i]为最后一个元素的间隔为gap的序列，比如说是：...,v [ i-2*gap],v [ i-gap],v [ i]，那么将v [ i]插入适当的位置中，这样就能保证每个间隔为gap的序列都是最终有序的。
希尔排序最后就是把gap一直缩小到0达到最终的有序状态的，对于内部的两层循环，我们用数据来枚举
假设我们当时以v [ i]结尾的间隔为gap的序列已经是有序的了，就是...,v [ i-2*gap],v [ i-gap],v [ i]是有序的，那么第二层for循环进入到i变为i+gap的时候，这时候进行的就是将v [ i+gap]插入到...,v [ i-2*gap],v [ i-gap],v [ i]这个序列中适当的位置，此时...,v [ i-2*gap],v [ i-gap],v [ i],v [ i+gap]就是有序的了，这样i从gap取到n-1就保证所有间隔为gap的序列都是有序的了，不知道说了这么多说明白了没有

[ 本帖最后由 daybreakcx 于 2009-5-28 18:12 编辑 ]

bsdwiki

多谢楼上前辈，我消化消化先

大致意思我看懂了，第一层循环控制增量，第二层循环控制在增量间移动，第三层循环负责间隔为增量的数据间比较，但我还是搞不懂
j -= gap 的意思，我笨死了！

[ 本帖最后由 bsdwiki 于 2009-5-29 01:16 编辑 ]