数据结构笔记 – 排序算法 希尔排序算法
本文由发表于6年前 | 数据结构与算法 | 评论数 3 |  被围观 7,972 views+

希尔排序:

将相距一个增量单位的元素集组成一个子集,然后通过以子集为单位对数据进行比较,最后得到子集间的数据是有序的,但是子集内德数据还未排序。这样继续缩小增量循环比较进行互换位置处理,直到增量变为1时为最后一次循环比较。

希尔排序算法突破了O(n^2)的时间复杂度。

#include <stdio.h>    

#define MAXSIZE 100  /* 待排序数组的大小 */

typedef struct
{
	int r[MAXSIZE+1];	/* 待排序数组r,r[0]为哨兵或临时变量 */
	int length;			/* 待排序数组的长度,为了方便理解,不包含r[0]元素 */
}SortList;

/* 希尔排序算法 */
void ShellSort(SortList *L)
{
	int i,j,k=0;
	/* 初始化增量为待排序数组的长度 */
	int increment=L->length;
	do
	{
		/* 设置增量 */
		increment=increment/3+1;
		for(i=increment+1; i<=L->length; i++)
		{
			/* 比较r[i]与r[i-increment]的值,即相差一个增量的元素相互比较 */
			if (L->r[i]<L->r[i-increment])
			{ 
				/* r[i]记录暂存到r[0]中 */
				L->r[0]=L->r[i]; 
				for(j=i-increment; j>0 && L->r[0]<L->r[j]; j-=increment) {
					L->r[j+increment]=L->r[j]; 
				}
				L->r[j+increment]=L->r[0];	/* 插入到相应位置 */
			}
		}
	}
	while(increment>1);
}
时间复杂度分析:

由于希尔排序是基于增量把数组分成几个子集的,从而实现了跳跃式的移动,提高了排序效率。

而增量大小的选择直接影响了排序的效率。研究表明当增量序列为increment[n]=2^(t-k+1) (0<=k<=t<=log2(n+1))时,排序的效率比较高,时间复杂度为O(n^(3/2))。

希尔排序是一种不稳定的排序算法。

除了文章中有特别说明,均为IT宅原创文章,转载请以链接形式注明出处。
本文链接:http://www.itzhai.com/data-structure-notes-hill-sorting-algorithm-sorting-algorithm.html
arthinking Java技术交流群:280755654,入门群:428693174 more
分享到:
 
如果您有更好的原创技术博文或者观点,欢迎投稿:admin@itzhai.com,或者关注订阅左侧浮动面板的微信号订阅IT宅itread)发送消息。
数据结构与算法推荐专题
文章评论
    3条评论
  1. hehg 2013年08月16日11:31:14  #-49楼 回复 回复

    你这图是用什么工具画得?

  2. ProcessOn 2013年08月20日16:19:21  #-48楼 回复 回复

    以后这类的就可以用ProcessOn画了

给我留言

有人回复时邮件通知我
数据结构与算法的相关文章
随机文章 本月热门 热评
1 JSF笔记 – MVC和JSF的介绍和下载使用 2011/12/1
2 8251A的编程约定 2011/4/24
3 Linux shell的使用和几个常见的实例解析 2011/6/11
4 jQuery插件实现的方法和原理简单说明 2012/8/8
5 8259A初始化过程步骤 2011/4/25
6 Java中使用Base64编码URL作为URL的参数 2011/9/12
友情推荐 更多
破博客 文官洗碗安天下,武将打怪定乾坤。多么美好的年代,思之令人泪落。
Mr.5's Life 白天是一名程序员,晚上就是个有抱负的探索者
行知-追寻技术之美 关注大数据,分布式系统
我爱编程 编程成长轨迹
Cynthia's Blog 学习笔记 知识总结 思考感悟
 
欢迎关注我的公众号 IT宅
关于IT宅 文章归档

IT宅中的文章除了标题注明转载或有特别说明的文章,均为IT宅的技术知识总结,学习笔记或随笔。如果喜欢,请使用文章下面提供的分享组件。转载请注明出处并加入文章的原链接。 感谢大家的支持。

联系我们:admin@itzhai.com

Theme by arthinking. Copyright © 2011-2015 IT宅.com 保留所有权利.