由來
? ??希爾排序是根據(jù)插入排序來實現(xiàn)的突诬。
????希爾排序根據(jù)插入排序的以下兩點性質(zhì)而提出的改進方法：
? ??????1.插入排序在對幾乎已經(jīng)順序排列的數(shù)據(jù)操作時念链，效率高盟步，即可以達到線性排序的效率征椒；
? ??????2.插入排序一般說來是低效的瑟捣。因為插入排序每次數(shù)據(jù)只能移動一位割疾。
? ??希爾排序算法利用了插入排序的簡單嚎卫，同時又避免了插入排序每次交換數(shù)據(jù)只能消除一個逆序的缺點。所以希爾排序一般不是交換相鄰的元素宏榕，而是跳躍一段距離進行交換拓诸。
原理
? ??希爾排序通過將整個待排序元素序列分成若干個子序列（由相隔某個“增量”的元素組成）分別直接進行插入排序。然后依次縮減增量再次進行排序麻昼，待整個序列中的元素基本有序奠支，即增量足夠小時，再對全體進行元素進行一次直接插入排序抚芦。因為最后一次插入排序是基于有序序列的插入排序倍谜，效率是很高的。因此希爾排序在時間上是優(yōu)于直接插入排序的叉抡。
步長序列
? ??步長序列是希爾排序的核心部分尔崔。只要最終步長為1，任何步長序列都可以工作褥民。算法最開始以一定的步長進行排序季春。初次排序完畢之后，再次根據(jù)既定步長進行排序消返。最終算法是以步長為1進行排序耘拇。當(dāng)步長為1的時候宇攻，算法演變?yōu)椴迦肱判颉?/p>
算法效率
? ??最優(yōu)時間為O（n）尺碰，不穩(wě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))
