Chinaunix首页 | 论坛 | 博客
  • 博客访问: 4774086
  • 博文数量: 291
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 7924
  • 用 户 组: 普通用户
  • 注册时间: 2016-07-06 14:28
个人简介

阿里巴巴是个快乐的青年

文章分类

全部博文(291)

文章存档

2018年(21)

2017年(4)

2016年(5)

2015年(17)

2014年(68)

2013年(174)

2012年(2)

分类: 架构设计与优化

2013-04-30 23:32:59

一、数据结构
        约定排序均为升序排序,要排序的记录存储在线性表中,线性表由排序关键字和其它域组成,其定义如下:
        #define MAXITEM 100
        struct rec
        {
            KeyType key;        // 关键字域
            ElemType data;     // 其它数据域
        };
        struct rec sqlist[MAXITEM];
        这里的KeyType和ElemType可以是任何相应的数据类型,比如int,float或char等,在算法中,约定其为int类型。

二、算法思想
        希尔(Shell)排序的基本思想是:把记录按下标的一定增量分组,对每组记录使用插入排序,随着增量逐渐减小,所分成的组包含的记录越来越多,到增量的值减小到1时,整个数据合成为一组,构成一组有序记录,则完成排序。

三、程序实现
        实现希尔排序的函数如下:
        void shellsort(sqlist r, int n)        // 排序元素r[1]~r[n]
        {
            int i, j, gap;
            struct rec x;
            gap = n/2;
            while (gap > 0)
            {
                for (i=gap+1; i<=n; i++)
                {
                    j = i - gap;
                    while (j > 0)
                    {
                        if (r[j].key > r[j+gap].key)  
                        {
                            x = r[j];        // 将r[j]与r[j+gap]进行交换
                            r[j] = r[j+gap];
                            r[j+gap] = x;
                            j = j - gap;
                        }
                        else
                        {
                            j = 0;
                        }
                    }
                    gap = gap / 2;        // 减小增量
                }
            }
        }
        希尔排序的实质还是一种插入排序,但它是一种不稳定的排序方法。希尔排序算法的时间复杂度是O(nlog2n)。



阅读(2679) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~