希爾排序（以發明者的名字命名），也稱 `遞減增量` 排序算法，是 `插入排序` 的一種更高效的改進版本。
實際思路：
1. 先拆分成N個組的子數組
2. 對每個子數組進行插入排序，讓子數組有序
3. 再拆分成 N 個子數組
4. 對每個子數組進行插入排序，讓子數組有序
.... 直到無法再拆分為止。
拆分原理：
第一次的跨度：用數組長度/2
第二次的跨度：上一次的跨度/2
直到跨度為0結束
前提：需要先對插入排序有較深的理解。
# 實現思路
# JavaScript
~~~
function shellSort(arr) {
// 計算跨度
let gap = parseInt(arr.length/2)
// 保存臨時數據
let tmp
// 當跨度大于0時（跨度每次減半）
while(gap>0) {
/* 對每個跨度對應的組執行 “插入排序” */
// 插入排序是從第2 個元素開始向前面的比較
// 所以這里開始的元素是 gap （向后一個跨度）即第2個元素
for(let i=gap; i<arr.length; i++) {
// 保存當前元素
tmp = arr[i]
// 對同一跨度組的前面的元素進行比較
// 如果前一個元素大于這個元素，那么前一個
// 元素就向后挪一位，直到一個不大于當前元素的就退出循環（不需要再向前比較了）
for(var j=i-gap;j>=0 && tmp<arr[j];j-=gap) {
arr[j+gap] = a[j]
}
// 把當前元素放到不大于它的這個元素的后面
arr[j+gap]=tmp
}
// 跨度減小一半
gap = parseInt(gap/2)
}
return arr
}
~~~
