文档章节

java 数据结构-->希尔排序

狂奔啦蜗牛
 狂奔啦蜗牛
发布于 2012/08/22 21:06
字数 388
阅读 103
收藏 1

【推荐】2019 Java 开发者跳槽指南.pdf(吐血整理) >>>

    希尔排序(Shell Sort)又称缩小增量排序算法的基本思路是:先取一个小于n的整数(称为增量)然后把排序中的n个记录分为若干个子表从下标0开始间隔为i的记录组成一个子表在各个子表内进行直接插入排序随着增量的减小达到排序目的。

算法性能分析:

(1)      空间复杂度  希尔排序用到了直接插入排序所以空间复杂度为O1

2  时间复杂度  O(n ^2

3)算法的稳定性  不稳定的排序算法

	/*
	 * Kiss_My_Love
	 * 2012/8/22
	 * 希尔排序
	 **/
public static void shellArray(Object[] a){
        for(int i=a.length/2;i>0;i/=2){ //对排序数列设置增量,并确定外围循环次数
		for(int j=0;j<i;j++){
			insertSort(a,j,i);//单位数组进行排序
		}
	}
}
private static void insertSort(Object[] A, int start, int d) {
	int t;
	for (int i = start + d; i < A.length; i += d) {
	  for (int j = i; (j >= d) && ((Integer)A[j] <(Integer) A[j - d]); j -= d) {
			t = (Integer) A[j];
			A[j] = A[j - d];
			A[j - d] = t;
			}
		}

听所还有一个更加犀利的算法比较NB现在和大家一起分享 这个是别人写的给大家拿出来好好看看:

/*
	 * Kiss_My_Love
	 * 2012/8/23
	 * 希尔排序
	 **/
public static Object[] shellSort(Object[] arr){
			int i,j,n=1,temp,len = arr.length;
			while(n<=len/3)
				n = n*3+1;
			while(n > 0){
				for (i = n; i < len; i++) {
					temp = (Integer) arr[i];
					j = i;
					while(j >= n &&  (Integer)arr[j - n] >= temp){
						arr[j] = arr[j - n];
						j-=n;
					}
					arr[j] = temp;
				}
				n = (n - 1)/3;
			}
		return arr;
		}


© 著作权归作者所有

狂奔啦蜗牛
粉丝 8
博文 17
码字总数 15025
作品 0
西安
程序员
私信 提问
可视化的数据结构和算法

还记得之前发布过的那个关于可视化排序的文章吗?在网上又看到了一个旧金山大学David Galles做的各种可视化的数据结构和基本算法的主页,网址在这里,大家可以看看。我把这个页面的目录列在下...

戴威
2011/05/12
1K
5
可视化的数据结构和算法

还记得之前发布过的那个关于可视化排序的文章吗?在网上又看到了一个旧金山大学David Galles做的各种可视化的数据结构和基本算法的主页,网址在这里,大家可以看看。我把这个页面的目录列在下...

戴威
2011/05/12
20
0
《数据结构与算法系列》合集整理

《数据结构与算法系列》合集整理 整理来自博客园skywang12345,以下摘自作者介绍: “最近抽空整理了"数据结构和算法"的相关文章。在整理过程中,对于每种数据结构和算法分别给出"C"、"C++"...

kaixin_code
2018/12/01
232
0
java 通配符的应用— java 排序算法

这几天无聊,又重新学起java的排序算法,为DualPivotQuickSort做准备。为了更好地适应各种情况,我们选择使用通用类型T和通配符的上下界来实现,同时这次谈的是对数组对象的排序。如果你对j...

天地一MADAO_
2014/03/02
122
0
推荐十大经典排序算法,再也不用担心面试了!

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见的内部排序算法有:...

Java面经
07/15
143
0

没有更多内容

加载失败,请刷新页面

加载更多

如何管stderr,而不是stdout?

我有一个要写入信息的程序stdout和stderr ,我需要grep通过什么是未来标准错误 ,而忽视标准输出 。 我当然可以分2步完成: command > /dev/null 2> temp.filegrep 'something' temp.file...

技术盛宴
17分钟前
4
0
centos7.5上通过docker安装并运行mysql5.7

1. docker pull mysql:5.7 2. docker run --name mysql5.7 -p 3306:3306 -e MYSQL_ROOT_PASSWORD=123456 -d mysql:5.7...

Ryub
20分钟前
4
0
什么是比赛条件?

在编写多线程应用程序时,遇到的最常见问题之一是竞争条件。 我对社区的问题是: 什么是比赛条件? 您如何检测到它们? 您如何处理它们? 最后,如何防止它们发生? #1楼 当设备或系统试图同...

javail
32分钟前
4
0
SpringMVC源码分析-DispatcherServlet-init方法分析

上一篇:SpringMVC源码分析-DispatcherServlet实例化干了些什么 先吐槽一下。。。写了两小时的博客突然被俺家小屁孩按了刷新,东西不见了,建议OSCHINA能够自动定时保存啊。让我先安静一下。...

特拉仔
39分钟前
4
0
python协程 生成器

协程,又称微线程,纤程。英文名Coroutine。 线程是系统级别的它们由操作系统调度,而协程则是程序级别的由程序根据需要自己调度。在一个线程中会有很多函数,我们把这些函数称为子程序,在子...

沙门行道
50分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部