希爾排序

希爾排序是先將整個待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進(jìn)行依次直接插入排序。

將待排序數(shù)組按照步長gap進(jìn)行分組，然后將每組的元素利用直接插入排序的方法進(jìn)行排序；每次再將gap折半減小，循環(huán)上述操作；當(dāng)gap=1時，利用直接插入，完成排序。

一般來說最簡單的步長取值是初次取數(shù)組長度的一半為增量，之后每次再減半，直到增量為1。

算法描述：

①. 選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；（一般初次取數(shù)組半長，之后每次再減半，直到增量為1）
②. 按增量序列個數(shù)k，對序列進(jìn)行k 趟排序；
③. 每趟排序，根據(jù)對應(yīng)的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進(jìn)行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

也即是：

1. 得到gap 數(shù)組：一般初次取數(shù)組半長，之后每次再減半，直到增量為1

2. gap 數(shù)組的長度就是排序的趟數(shù)，每一個趟都要根據(jù)gap切割數(shù)組成若干個不同長度的序列，對每個序列進(jìn)行插入排序

    function shellSort(arr){
        var gap=arr.length/2;
        for(;gap>0;gap/=2){//控制排序的總趟數(shù)，不同的gap值都要來一遍
            for (var j=0;(j+gap)<arr.length;j++) {//開始每個gap的組內(nèi)排序，邏輯上的分組，排序與分組是同時進(jìn)行的
                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())//打印出當(dāng)前排序的數(shù)組
                    }
                }
            }
        }
    }