文档章节

Shell(希尔)排序

JiaChang
 JiaChang
发布于 2016/08/13 21:08
字数 782
阅读 10
收藏 1

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
海口
程序员
私信 提问
【译】Swift算法俱乐部-希尔排序

本文是对 Swift Algorithm Club 翻译的一篇文章。 Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目,目前在GitHub上有18000+⭐️,我初略统计了一下...

Andy_Ron
11/05
0
0
排序算法之冒泡,选择,插入和希尔

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

2017/12/28
0
0
输入排序算法的名字与待排序的数据列可完成数据排序?

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

禧禧的禧
2014/06/07
107
0
2、希尔排序(Shell`s Sort)

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

驛路梨花醉美
2016/07/25
39
0
希尔排序算法

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

laymanxia
2014/04/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

如何解决 homebrew 更新慢的问题

之前一直困扰于 Homebrew 的更新速度,曾试过修改更新源(清华、中科大等)的方式,但是并没什么卵用;也试过设置 curl 代理的方式,但是 brew 走的好像不是 curl 的方式,所以也没用。 通过...

whoru
11分钟前
0
0
TiDB EcoSystem Tools 原理解读系列(二)TiDB-Lightning Toolset 介绍

简介 TiDB-Lightning Toolset 是一套快速全量导入 SQL dump 文件到 TiDB 集群的工具集,自 2.1.0 版本起随 TiDB 发布,速度可达到传统执行 SQL 导入方式的至少 3 倍、大约每小时 100 GB,适合...

TiDB
13分钟前
0
0
【Visual Studio 扩展工具】如何在ComponentOneFlexGrid树中显示RadioButton

概述 在ComponentOne Enterprise .NET控件集中,FlexGrid表格控件是用户使用频率最高的控件之一。它是一个功能强大的数据管理工具,轻盈且灵动,以分层的形式展示数据(数据呈现更加直观)。...

葡萄城技术团队
16分钟前
0
0
Maven环境隔离

Maven环境隔离 1. 什么是Maven环境隔离 顾名思义,Maven环境隔离就是将开发中的环境与beat环境、生产环境分隔开,方便进行开发和维护。这个在实际项目中用的还是很多的,如果你的项目用的Mav...

蚂蚁-Declan
16分钟前
1
0
day182-2018-12-19-英语流利阅读-待学习

“性感”时代已去,维密将如何转身? Daniel 2018-12-19 1.今日导读 维多利亚的秘密(Victoria's Secret)这个内衣品牌,最近似乎步入了“中年危机”——曾经打遍天下的“性感”内衣,在主打...

飞鱼说编程
16分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部