Shell 排序

分类: 算法 C 2008-09-17 11:02 1898人阅读 评论(4) 举报
刚才在CSDN的C语言板块看到了有人说Shell排序的问题,所以一起学习了一下,并进行如下总结

shell排序的思想是根据步长由长到短分组,进行排序,直到步长为1为止,属于插入排序的一种。下面用个例子更好的理解一下

无序数列: 32, 43,56,99,34,8,54,76

1.首先设定gap=n/2=4于是分组
32,34    排序  32,34
43, 8             8, 43
56,54            54,56
99,76            76,99
数列变成 32,8,54,76,34,43,56,99

2.gap=gap/2=2 于是分组
32,54,34,56  排序  32,34,54,56
8,76,43,99            8,43,76,99
于是数列变成 32,8,34,43,54,76,56,99

3.gap=gap/2=1于是分组
32,8,34,43,54,76,56,99 排序
8,32,34,43,54,56,76,99
gap=1结束……

相应的C语言代码引用K&R C程序设计一书中给出的代码

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){ //比较相距gap的元素,逆序互换//我看不懂为啥是个for不是if 20140220
            temp=v[j];
            v[j]=v[j+gap];
            v[j+gap]=temp;
       }
}

以上就为Shell排序的相关总结,以后想到的再添加……

更多
0

 
查看评论
4楼 insulted 2009-08-17 12:19发表 [回复]
ZT Shell 排序-LMLPHP
当然了,博主原来的代码看起来更紧凑简洁一些,呵呵!
3楼 insulted 2009-08-17 12:15发表 [回复]
ZT Shell 排序-LMLPHP
如果要体现博主中说的“属于插入排序的一种”的话,最好的代码应该是这样子的:
for(gap=n/2;gap&gt;0;gap/=2) //设定步长
for(i=gap;i&lt;n; i) //在元素间移动为止
{
if (v[i] &lt; v[i-gap])
{
temp = v[i];
for (j=i-gap; j&gt;=0 &amp;&amp; temp&lt;v[j]; j-=gap)
v[j gap] = v[j];
v[j gap] = temp;
}
}

请博主再看看

2楼 insulted 2009-08-17 11:58发表 [回复]
ZT Shell 排序-LMLPHP
博主中提到“shell排序的思想是根据步长由长到短分组,进行排序,直到步长为1为止,属于插入排序的一种。下面用个例子更好的理解一下”
但是最后给的code中的最内层循环,其实不是插入排序的实现,貌似是打擂台的冒泡排序。您再看看?
1楼 insulted 2009-08-17 09:47发表 [回复]
ZT Shell 排序-LMLPHP
very good!
thanks a lot!
05-11 15:02