排序-2- 希尔排序

希尔排序

希尔排序是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

将待排序数组按照步长gap进行分组，然后将每组的元素利用直接插入排序的方法进行排序；每次再将gap折半减小，循环上述操作；当gap=1时，利用直接插入，完成排序。

一般来说最简单的步长取值是初次取数组长度的一半为增量，之后每次再减半，直到增量为1。

算法描述：

①. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；（一般初次取数组半长，之后每次再减半，直到增量为1）
②. 按增量序列个数k，对序列进行k 趟排序；
③. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

也即是：

1. 得到gap 数组：一般初次取数组半长，之后每次再减半，直到增量为1

2. gap 数组的长度就是排序的趟数，每一个趟都要根据gap切割数组成若干个不同长度的序列，对每个序列进行插入排序

    function shellSort(arr){
        var gap=arr.length/2;
        for(;gap>0;gap/=2){//控制排序的总趟数，不同的gap值都要来一遍
            for (var j=0;(j+gap)<arr.length;j++) {//开始每个gap的组内排序，逻辑上的分组，排序与分组是同时进行的
                for(var i=0;(i+gap)<arr.length;i+=gap){//得到一组的一个序列
                    if(arr[i]>arr[gap+i]){//得到序列的过程同时排序
                        var temp=arr[i];
                        arr[i]=arr[i+gap];
                        arr[i+gap]=temp;
                        console.log(arr.toString())//打印出当前排序的数组
                    }
                }
            }
        }
    }