介绍

        前面的文章中我们介绍了插入排序的特点以及插入排序的二分插入进行性能的优化，接下来我们来研究一下插入排序的另一个变种排序：【希尔排序】。根据前面的经验我们得知插入排序的时间复杂度为O(n)-O(n^2)，这样虽然看起来性能很高，但是当我们插入排序的数据是一个完全倒序或者是反向数据过多的情况下插入排序需要比较的次数就会变多无限接近O(n^2),上次文章中我们通过分析插入排序在插入完成的部分是有序数组的情况进行了二分插入减少了比较次数，这次我们学习他的另外一个变种思路。

思路

        希尔排序也是考虑到插入排序当数据倒序情况太多而比较次数增多，所以希尔排序选择先将整体的数据大面积跳跃整理成有序的状态，最后逐渐变成一次插入排序，当最后执行插入排序的时候数组有序化渐渐形成所以需要比较的次数也会随之减少，但是希尔排序同样属于不稳定排序，所以他的时间复杂度并没有插入排序的最快情况高：O(n^(1.3—2)) 

图解

        希尔排序的过程相当于执行了多次插入排序对数组进行整理，所以我们要先定义一个步长，通常我们会将步长定义为数组长度的一半进行取整，然后每次整理将步长/2最终到步长为1的时候进行最后一次插入排序。我们仍然以之前的数组数据为例子。

let arr = [13,2,7,21,8,65,2,0,1,9,14,7,63]

这个数组的排序过程为下图展示的过程。

第一次以Math.floor(arr.length/2)的步长来进行分组插入排序

本次插入执行完毕之后的数组会变成如下样子

 

接下来我们继续进行步长的减小step=Math.floor(step/2),再次进行分组插入排序。如图。

 

观察上图可以发现我们将该数组分成了3小组进行插入排序，三个小组内部是有序的。接下来我们就是将 step=Math.floor(step/2),此时step的值已经减小为1，也就是变成了一次正常的插入排序

 

到这里我们变成功的将数据排序完毕，并且我们发现最后一次插入排序的比较次数已经很接近数组的长度了。这样便能在不适合插入排序的场景对插入排序做进一步的性能提升。

代码实现

let arr = [13,2,7,21,8,65,2,0,1,9,14,7,63]
/**
 * 希尔排序
 * @param {Object} arr 数组
 */
function sort(arr){
	//定义默认步长为数组的一半
	let step = Math.floor(arr.length/2)
	//让步长2阶递减到0
	while(step>0){
		//定义起始插入排序点
		let i = 0+step
		//执行按照步长的距离进行插入排序
		while(i<arr.length){
			//记录要比较的数据
			let temp = arr[i]
			//定义起始比较的数据
			let j = i-step
			//移动指针与j开始比较只要当前数据比前面的小就让前面的数据右移
			while(arr[j]>temp&&j>=0){
				arr[j+step] = arr[j]
				j-=step
			}
			//最后将数据插入到移动之后的位置
			arr[j+step] = temp
			//向右移动继续做分组插入
			i++
		}
			console.log(arr)
		//2阶递减
		step = Math.floor(step/2)
	}
}

 总结

        在众多排序算法中希尔排序属于很经典的一种排序，他利用了插入排序的原理做进一步的变种实现了一种新的排序思路，所以我们在编程中不要拘泥于一种模式和思路去固定的记录固定答案，“编程只有针对特定情况的最优解，并没有标准答案。”看懂这句话对我们编程思想的提升有很大的帮助。本次分享到此为止。