1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
1、算法描述
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
2、动图演示
849589-20180331170017421-364506073.gif
从图中我们可以得到以下算法总结
1 、比较前要把数组arr一分为二(arr1,arr2)，分到Math.floor(arrnN/2)=1为止
2 、假设排序n遍：
- 第0 ~（n-1）遍都是依次比较arr1和arr2的N位，如首先比较arr1[0]和arr2[0]，如果arr2[0]<arr1[0]那么久交换位置。
- 第n遍（最后一遍）排序会跟前面的元素从后往前依次进行一遍比较，直到找到比它大的元素的位置。
如图中最后一遍排序前顺序为50,70,60,80,61,84,83,88,87,89，对arr[2](60）进行比较时，先比较arr1,如果arr[2]<arr[1]则交换.如果arr[1]>arr[2]，arr[2]再与比较arr[0]。
3、代码实现
代码一：根据上图所总结的算法代码
//将整个arr均分为2半，分完后的arr变为arr1和arr2。
//例如 ： arr=[1,2,3,4],arr1=[1,2],arr2=[3,4]
function shellSort(arr){
var len=arr.length
for(var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)){//Math.floor(1/2)=0,所以在分割为1的时候，就结束了
for(var i=gap;i<arr.length;i++){
//最后一遍排序
if(gap==1){
var j=i;
var current=arr[i];
//从后往前比较，找到比arr[i-1]~arr[0]中比current大的元素
while((current<arr[j-gap])&&j>=0){
arr[j]=arr[j-gap];
j--;
}
arr[j]=current
}else{
if((arr[i]<arr[i-gap])){
////再比较依次arr1和arr2的n位也就是arr1[n],arr2[n]
var temp=arr[i];
arr[i]=arr[i-gap];
arr[i-gap]=temp;
}
}
}
}
return arr
}
代码二：原作者的代码（但是我还是不太理解）
function shellSort(arr) {
var len = arr.length;
for (var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
// 注意：这里和动图演示的不一样，动图是分组执行，实际操作是多个分组交替执行
for (var i = gap; i < len; i++) {
var j = i;
var current = arr[i];
while (j - gap >= 0 && current < arr[j - gap]) {
arr[j] = arr[j - gap];
j = j - gap;
}
arr[j] = current;
}
}
return arr;
}
