希尔排序

2020-04-19

字数统计: 730字 | 阅读时长≈ 2分

简介

对于插入排序来说，如果数组初始阶段越混乱，倒置元素对越多，那么插入排序所需要时间就越多，甚至达到N^2级别时间复杂度。而对于几乎已经排好序的数组来说，插入排序的性能又很高，可以达到线性排序的效率。因此对于这样的特点，对插入排序进行了改进，改进后的算法被称为希尔排序。

希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的h有序数组被称为h有序数组，也就是h个互相独立的有序数组交错在一起组成的一个数组。
实现希尔排序的方法思想：先将整个待排序的数组根据间隔h分割成多个子数组，对于这些子数组进行插入排序，然后不断的减少间隔h，重复这样的操作，等到整个数组基本有序时，再对整体记录进行插入排序即可。

具体分析

动图演示

strategy

算法实现与分析

public class Shell{
	public static void sort(Comparable[] a){
		int N = a.length;
		int h = 1;
		//初始间隔不能太小，如果太小，就没有与插入排序有太大不同
		while(h<N/3){
			h = 3*h + 1;
		}
		//当h==1时，就已经是最后一次插入排序了
		while(h>=1){

			//每次的h间隔排序
			for(int i = h; i < N; i++){
				//每次h间隔排序， 一个元素总是与比自己索引小h的元素进行比较。
				for(int j = i; j >= h && less(a[j],a[j-h]); j-=h){
					exch(a,j,j-h);
				}
			}

			//每轮h间隔排序结束，都需要将h减少，然后开始下一轮，直到h=1，进行常规插入排序
			h = h/3;
		}
	}
}

对于希尔排序，目前最重要的结论是它的运行时间达不到平方级别，在目前已知最坏情况下，希尔排序的比较次数和 N^(3/2)成正比。

在对希尔排序进行思考之后，我认为它之所以能比插入排序表现出更优异的性能就在于在算法开始阶段，允许两个间隔一段距离的元素进行比较和交换。
例如： 1 7 6 4 3 9 10
当对其中的 7 和 3 进行交换后，就变成了 1 3 6 4 7 9 10
对于原序列，倒置对数为：6
对于现序列，倒置对数为：1
由于允许跨距离访问，在元素交换之后，会顺带解决一些与距离之中元素的倒置问题，我个人认为这应该是希尔排序性能优于插入排序的原因或者原因之一。

参考

本文作者： xczll
本文链接： https://xczllgit.github.io/2020/04/19/algorithm/2020-04-19-shellSort/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！