排序算法之希尔排序原理与实战

JAVA herman 1182浏览 0评论
公告:“业余草”微信公众号提供免费CSDN下载服务(只下Java资源),关注业余草微信公众号,添加作者微信:xttblog,发送下载链接帮助你免费下载!
本博客日IP超过1800,PV 2600 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:xttblog,之前的微信号好友位已满,备注:返现
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序
视频教程免费领

说到希尔排序我就想到了插入排序,因为希尔排序是基于插入排序的以下两点性质而提出改进方法的:
1.插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率。
2.但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。

以下列出小编对各种排序算法的性能测试的结果,仅供大家参考(性能测试20000大小随机数组):

排序算法 所用时间
bubbleSort 766 ms
bubbleSortAdvanced 662 ms
bubbleSortAdvanced2 647 ms
selectSort 252 ms
insertSort 218 ms
insertSortAdvanced 127 ms
insertSortAdvanced2 191 ms
binaryTreeSort 3 ms
shellSort 2 ms
shellSortAdvanced 2 ms
shellSortAdvanced2 1 ms
mergeSort 3 ms
quickSort 1 ms
heapSort 2 ms

通过分析比较希尔排序在效率上还是很理想的。下面将详细讲解希尔排序的原理和实践。
基本思想是先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高。
下图为希尔排序的排序分解过程:

希尔排序的完整实现代码如下:

public static void test0(){
	int[]a={49,38,65,97,76,13,27,49,78,34,12,64,1};
    int d=a.length;
	while(true){
		d=d/2;
		for(int x=0;x<d;x++){
			for(int i=x+d;i<a.length;i=i+d){
				int temp=a[i],j;
				for(j=i-d;j>=0&&a[j]>temp;j=j-d){
					a[j+d]=a[j];
				}
				a[j+d]=temp;
			}
		}
		if(d==1)
			break;
	}// 排序结果如下
	for(int i=0;i<a.length;i++){
		System.out.print(a[i]+" ");
	}
}
public static void test1(){
	while(true){
		for(int i=0;i<d;i++){
			for(int j=i;j+d<a.length;j+=d){
				int temp;
				if(a[j]>a[j+d]){
					temp=a[j];
					a[j]=a[j+d];
					a[j+d]=temp;
				}
			}
		}
		if(d==1)
			break;
		d--;
	}
}
public static void main(String [] args){
	test0();
	test1();
}

版权声明:本文为博主原创文章,未经博主允许不得转载。原文地址http://www.xttblog.com/?p=443

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加QQ1群:135430763(2000人群已满),QQ2群:454796847(已满),QQ3群:187424846(已满)。QQ群进群密码:xttblog,想加微信群的朋友,之前的微信号好友已满,请加博主新的微信号:xttblog,备注:“xttblog”,添加博主微信拉你进群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作可添加助理微信进行沟通!

本文原文出处:业余草: » 排序算法之希尔排序原理与实战