希尔排序（以发明者的名字命名），也称 `递减增量` 排序算法，是 `插入排序` 的一种更高效的改进版本。
实际思路：
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
}
~~~
