文档章节

Shell(希尔)排序

JiaChang
 JiaChang
发布于 2016/08/13 21:08
字数 782
阅读 8
收藏 1
点赞 0
评论 0

Shell(希尔)排序

    对于直接插入排序而言,如果一个很小的数据单元位于很靠近右端的位置上,为了把这个数据单元移动到左边正确的位置上,中间所有的数据单元都需要向右移动一格。这个步骤对每一个数据项都执行了近n次复制。虽然不是所有的数据项都必须移动n个位置,但平均下来,每个数据项都会移动n/2格,总共是n*n/2次复制。因此,直接插入排序的执行效率是O(n^2)[注:这里是n的平方]

    Shell排序对直接插入排序进行了简单的改进:它通过加大插入排序中元素之间的间隔,并在这些有间隔的元素中进行插入排序,从而使数据项大跨度地移动,当这些数据项经过一趟排序之后。Shell排序算法减少数据项的间隔再进行排序,依次进行下去。这些进行排序的数据项之间的间隔被称为增量,习惯上用h来表示这个增量,并且满足以下公式 :

                        h = 3*h+1反过来 h = (h-1)/3

    当h值很大的时候,数据项每一趟排序需要移动元素的个数非常少,但数据项移动的距离非常长,这是非常有效率的。当h减少时,每一趟排序需要移动的元素个数增多,但此时数据项已经接近于它们排序后最终的位置,这对于插入排序可以更有效率。(直接使用增量为1的Shell排序就是直接插入排序

Shell排序的实现

	/**
	 * Shell(希尔)排序
	 * @param data 待排序数组
	 */
	public static void shellSort(int[] data){
		//先求增量
		int h = 1;
		//按 3*h+1 得到最大的增量
		while(h <= data.length/3){
			h = 3*h+1;
		}
		while(h > 0){
			for(int i = h; i<data.length; i++){
				//i索引处的值已经比前面的所有值都大,表明已经有序,无序插入
				//(i-h 索引之前的数据已经有序,i-h索引处的元素的值就是最大值)
				if(data[i-h] > data[i]){
					//当数据整体后移时,保证data[i]处的元素不丢失
					int temp = data[i];
					//最多后移多少个元素
					int j = i-h;
					//循环判断,只要前面的元素比data[i]大,则需要后移,注意这里是j-=h而不是j--
					for(;j>=0 && data[j] > temp; j-=h){
						data[j+h] = data[j];
					}
					//最后将temp插入到合适的位置
					data[j+h] = temp;
				}
			}
			//依据增量公式,计算下一个增量
			h = (h-1)/3;
		}
	}


测试代码

 

算法分析

(1)时间复杂度:O(n^3/2)~O(n^7/6)

(2)空间复杂度::O(1)

(3)Shell排序是不稳定的

(4)只能用于顺序结构,不能用于链式结构

(5)记录总的比较次数和移动次数都比直接插入排序要少,n越大时,效果越明显。所以适合初始记录无序,n较大时的情况。

 

 

 

© 著作权归作者所有

共有 人打赏支持
JiaChang
粉丝 2
博文 32
码字总数 18002
作品 0
海口
程序员
输入排序算法的名字与待排序的数据列可完成数据排序?

拜托各位大神了 1.通过程序实现排序算法,算法支持冒泡排序、插入排序、希尔选择,且可扩展算法。只需要输入排序算法的名字与待排序的数据列表即可完成数据排序; 三个算法的代码写出来了,后...

禧禧的禧 ⋅ 2014/06/07 ⋅ 0

希尔排序算法

希尔排序(Shell Sort)是 D.L.Shell 于1959 年提出来的一种排序算法,在这之前排序算法的时间复杂度基本都是O(n2)的,希尔排序算法是突破这个时间复杂度的第一批算法之一。 直接插入排序,应...

laymanxia ⋅ 2014/04/13 ⋅ 0

2、希尔排序(Shell`s Sort)

基本思想 先取一个小于n的整数d1作为第一个增量,把待排序的全部记录分成dx个组。所有距离为d1的倍数的记录放在同一个组中。 先在各组内进行直接插人排序。 然后,取第二个增量d2<d1重复上述...

驛路梨花醉美 ⋅ 2016/07/25 ⋅ 0

排序算法之冒泡,选择,插入和希尔

冒泡排序(Bubble Sort) 冒泡排序的核心部分是双重嵌套循环,持续比较相邻元素,大的挪到后面,因此大的会逐步往后挪,故称之为冒泡。 算法思路 比较相邻的元素。如果第一个比第二个大,就交换...

⋅ 2017/12/28 ⋅ 0

java排序之快速排序、归并排序、基数排序

前两篇说了Java排序中的冒泡、选择、插入、希尔等排序算法,今天就探讨一下剩下的三种常用排序。 快速排序: 当要求时间最快时,就可以用快速排序算法。 选择第一个数为p,小于p的数放在左边...

野小疯 ⋅ 06/05 ⋅ 0

Python 排序的姿势,你们,你们还要学习..学习一个

在python 中当然可以是使用各种方法实现各种排序方法,快排、希尔、插入等等,但是用python去实现的各种排序方法的效率不一定会很高,所以在python代码中,遇到排序问题的时候还是推荐使用p...

Archer弓兵 ⋅ 2016/09/01 ⋅ 0

排序(一)

(一) 插入排序(insertion sort): 是最简单的排序算法之一,插入排序由 N - 1 趟排序组成。对于 P = 1 趟到 P = N - 1 趟,插入排序保证从位置 0 到 位置 P 的元素为已排序状态。一般方法...

passionfly ⋅ 2014/11/02 ⋅ 0

各种排序方法总结

代码全部重新编写,去掉了一些很dirty的地方,并增加了几种排序方法。 现在一共收录了插入,选择,冒泡,归并,希尔,堆排,快排,计数等八种常用的排序方法,并做了效率比较,其中对1万个随...

扶殊88 ⋅ 2011/11/29 ⋅ 0

[数据结构]插入排序与希尔排序

简述 直接插入排序是一种最简单的排序方法,基本操作是讲一个记录插入到已排好的有序数列中。 简单来说,将一乱序数列分成已排好和未排好两部分。每次从未排好部分取出一个数,将其插入到已排...

小弘 ⋅ 2014/06/11 ⋅ 0

C 扩展类库--celib

celib 是使用ANSI C开发的一个扩展类库(c extend library),包含了一些常用的数据结构和算法的封装,可以应用到项目或者用于学习。 目前已经包含的封装如下: (01). 动态数组。 (02). bitmap...

狮子的魂 ⋅ 2014/01/03 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Spring | IOC AOP 注解 简单使用

写在前面的话 很久没更新笔记了,有人会抱怨:小冯啊,你是不是在偷懒啊,没有学习了。老哥,真的冤枉:我觉得我自己很菜,还在努力学习呢,正在学习Vue.js做管理系统呢。即便这样,我还是不...

Wenyi_Feng ⋅ 今天 ⋅ 0

博客迁移到 https://www.jianshu.com/u/aa501451a235

博客迁移到 https://www.jianshu.com/u/aa501451a235 本博客不再更新

为为02 ⋅ 今天 ⋅ 0

win10怎么彻底关闭自动更新

win10自带的更新每天都很多,每一次下载都要占用大量网络,而且安装要等得时间也蛮久的。 工具/原料 Win10 方法/步骤 单击左下角开始菜单点击设置图标进入设置界面 在设置窗口中输入“服务”...

阿K1225 ⋅ 今天 ⋅ 0

Elasticsearch 6.3.0 SQL功能使用案例分享

The best elasticsearch highlevel java rest api-----bboss Elasticsearch 6.3.0 官方新推出的SQL检索插件非常不错,本文一个实际案例来介绍其使用方法。 1.代码中的sql检索 @Testpu...

bboss ⋅ 今天 ⋅ 0

informix数据库在linux中的安装以及用java/c/c++访问

一、安装前准备 安装JDK(略) 到IBM官网上下载informix软件:iif.12.10.FC9DE.linux-x86_64.tar放在某个大家都可以访问的目录比如:/mypkg,并解压到该目录下。 我也放到了百度云和天翼云上...

wangxuwei ⋅ 今天 ⋅ 0

PHP语言系统ZBLOG或许无法重现月光博客的闪耀历史[图]

最近在写博客,希望通过自己努力打造一个优秀的教育类主题博客,名动江湖,但是问题来了,现在写博客还有前途吗?面对强大的自媒体站点围剿,还有信心和可能型吗? 至于程序部分,我选择了P...

原创小博客 ⋅ 今天 ⋅ 0

IntelliJ IDEA 2018.1新特性

工欲善其事必先利其器,如果有一款IDE可以让你更高效地专注于开发以及源码阅读,为什么不试一试? 本文转载自:netty技术内幕 3月27日,jetbrains正式发布期待已久的IntelliJ IDEA 2018.1,再...

Romane ⋅ 今天 ⋅ 0

浅谈设计模式之工厂模式

工厂模式(Factory Pattern)是 Java 中最常用的设计模式之一。这种类型的设计模式属于创建型模式,它提供了一种创建对象的最佳方式。 在工厂模式中,我们在创建对象时不会对客户端暴露创建逻...

佛系程序猿灬 ⋅ 今天 ⋅ 0

Dockerfile基础命令总结

FROM 指定使用的基础base image FROM scratch # 制作base image ,不使用任何基础imageFROM centos # 使用base imageFROM ubuntu:14.04 尽量使用官方的base image,为了安全 LABEL 描述作...

ExtreU ⋅ 昨天 ⋅ 0

存储,对比私有云和公有云的不同

导读 说起公共存储,很难不与后网络公司时代的选择性外包联系起来,但尽管如此,它还是具备着简单和固有的可用性。公共存储的名字听起来也缺乏专有性,很像是把东西直接堆放在那里而不会得到...

问题终结者 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部