由来
希尔排序是根据插入排序来实现的。
希尔排序根据插入排序的以下两点性质而提出的改进方法：
1.插入排序在对几乎已经顺序排列的数据操作时，效率高，即可以达到线性排序的效率；
2.插入排序一般说来是低效的。因为插入排序每次数据只能移动一位。
希尔排序算法利用了插入排序的简单，同时又避免了插入排序每次交换数据只能消除一个逆序的缺点。所以希尔排序一般不是交换相邻的元素，而是跳跃一段距离进行交换。
原理
希尔排序通过将整个待排序元素序列分成若干个子序列（由相隔某个“增量”的元素组成）分别直接进行插入排序。然后依次缩减增量再次进行排序，待整个序列中的元素基本有序，即增量足够小时，再对全体进行元素进行一次直接插入排序。因为最后一次插入排序是基于有序序列的插入排序，效率是很高的。因此希尔排序在时间上是优于直接插入排序的。
步长序列
步长序列是希尔排序的核心部分。只要最终步长为1，任何步长序列都可以工作。算法最开始以一定的步长进行排序。初次排序完毕之后，再次根据既定步长进行排序。最终算法是以步长为1进行排序。当步长为1的时候，算法演变为插入排序。
算法效率
最优时间为O（n），不稳定
javaScript
let arr1 = [2, 34, 12, 67, 46, 5, 10]
function shellSort(arr){
let reArr = []
if(Array.isArray(arr) && arr.length > 0){
reArr = reArr.concat(arr)
let h = 1 // 保存可变增量
while(h <= reArr.length / 3){
h = h * 3 + 1 // 得到增量序列的最大值
}
while(h > 0){
console.log('h ===>', h)
for(let i = h; i < reArr.length; i++){
let current = reArr[i]
if(current < reArr[i-h]){
let j = i - h
// 整体后移
for(; j>0 && reArr[j] > current; j -= h){
reArr[j+h] = reArr[j]
}
reArr[j+h] = current
}
console.log('reArr===>', reArr)
}
h = (h - 1) / 3
}
}
return reArr
}
console.log('ARR ==>', shellSort(arr1))
网友评论