希尔排序（缩小增量排序）

//选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
//按增量序列个数k，对序列进行k 趟排序；
//每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。
//仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
//它与插入排序的不同之处在于，它会优先比较距离较远的元素

//时间复杂度：最好的情况原本就是有序O(n) 最坏的情况 O（n的平方） 平均O（n的1.3次方）
//空间复杂度：O（1）
        var arr = [49,38,65,97,76,13,27,48,55,4];
        function ShellPass(arr,d){
            var len = arr.length;
            var temp;
            for(var i=d;i<len;i++){
                if(arr[i]<arr[i-d]){
                    temp = arr[i];
                    j = i-d;
                    while(j>=0&&temp<arr[j]){
                        arr[j+d] = arr[j];
                        j = j-d;
                    }
                    arr[j+d] = temp;
                }
            }
        }
        function ShellSort(arr) {
            var increment = arr.length;
            while(increment>1){
                increment = Math.floor(increment/2);
                ShellPass(arr,increment);
            }
            return arr;
        }
        console.log(ShellSort(arr));//4, 13, 27, 38, 48, 49, 55, 65, 76, 97