注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Mr.Right

不顾一切的去想,于是我们有了梦想。脚踏实地的去做,于是梦想成了现实。

 
 
 

日志

 
 
关于我

人生一年又一年,只要每年都有所积累,有所成长,都有那么一次自己认为满意的花开时刻就好。即使一时不顺,也要敞开胸怀。生命的荣枯并不是简单的重复,一时的得失不是成败的尺度。花开不是荣耀,而是一个美丽的结束,花谢也不是耻辱,而是一个低调的开始。

网易考拉推荐

阿英讲希尔排序Shell Sort -- C语言实现  

2012-08-11 21:00:14|  分类: 编程 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
希尔排序的实质就是分组插入排序,该方法又称缩小增量排序。

该方法的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高。

 

以n=10的一个数组49, 38, 65, 97, 26, 13, 27, 49, 55, 4为例

第一次 gap = 10 / 2 = 5

49   38   65   97   26   13   27   49   55   4

1A                                            1B

        2A                                            2B

                   3A                                          3B

                            4A                                           4B

                                     5A                                            5B

1A,1B,2A,2B等为分组标记,数字相同的表示在同一组,大写字母表示是该组的第几个元素, 每次对同一组的数据进行直接插入排序。即分成了五组(49, 13) (38, 27) (65, 49)  (97, 55)  (26, 4)这样每组排序后就变成了(13, 49)  (27, 38)  (49, 65)  (55, 97)  (4, 26),下同。

第二次 gap = 5 / 2 = 2

第一次组内插入排序后

13   27   49   55   4    49   38   65   97   26

1A             1B              1C              1D               1E

        2A                2B              2C               2D              2E

第三次 gap = 2 / 2 = 1

第二次组内插入排序后

4   26   13   27   38    49   49   55   97   65

1A   1B     1C    1D    1E      1F     1G    1H     1I     1J

第四次 gap = 1 / 2 = 0 排序完成得到数组:

第三次组内插入排序后

4   13   26   27   38    49   49   55   65   97


#include <stdio.h>

#include <stdlib.h>

void shellsort(int a[], int n)  

{  

    int j, gap;  

    //每次从数组第gap个元素开始,每个元素与自己组内的数据进行直接插入排序  

    for (gap = n / 2; gap > 0; gap /= 2)  

        for (j = gap; j < n; j++)//从数组第gap个元素开始, 按正常顺序a[j - gap]<a[j], 如不是的则执行组内插入排序

            if (a[j] < a[j - gap])  //第一次从1B的值a[gap]开始,先和1A的值a[0]比较,然后取2B的值a[gap+1]与2A的值a[1]比较              {  

                int temp = a[j];  

                int k = j - gap;  

                while (k >= 0 && a[k] > temp)  // 给temp在该组中找到合适的位置,注意分组时是a[k+gap], 不是a[k+1]哦

                {  

                    a[k + gap] = a[k];   // 注意分组后a[k]后移的位置是a[k+gap]

                    k -= gap;  

                }  

                a[k + gap] = temp;   

            }  

}  


int main()

{

    int i;

    int len;

    int array[] = {12, 278, 85, 24, 18, 69, 58, 21, 175, 28, 1};

    len = sizeof( array ) / sizeof( *array );

    printf( "排序前数组序列:\n" );

    for ( i = 0;i < len;i++ )

    {

        printf( "%5d", array[i] );

    }

    shellsort( array, len );

    printf( "\n排序后数组序列:\n" );

    for ( i = 0;i < len;i++ )

    {

        printf( "%5d", array[i] );

    }

    getchar();

}

 
  评论这张
 
阅读(575)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2016