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

公告：“业余草”微信公众号提供免费CSDN下载服务(只下Java资源)，关注业余草微信公众号，添加作者微信：xttblog2，发送下载链接帮助你免费下载！
本博客日IP超过2000，PV 3000 左右，急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包，请加博主新的微信号：xttblog2，之前的微信号好友位已满，备注：返现
受密码保护的文章请关注“业余草”公众号，回复关键字“0”获得密码
所有面试题(java、前端、数据库、springboot等)一网打尽，请关注文末小程序

腾讯云】1核2G5M轻量应用服务器50元首年，高性价比，助您轻松上云

说到希尔排序我就想到了插入排序，因为希尔排序是基于插入排序的以下两点性质而提出改进方法的：
1.插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
2.但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
以下列出小编对各种排序算法的性能测试的结果，仅供大家参考(性能测试20000大小随机数组)：

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

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

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）！可加作者微信号：xttblog2。备注：“1”，添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注！后续有精彩内容会第一时间发给您！原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系！

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