最近我們進入了排序算法專題，上節課聊到了"簡單"插入排序，那在簡單的基礎上，我們可以怎麼做進一步的優化呢，這篇來看看優化版--**希爾排序**！
大家好，我是melo，一名大二上軟體工程在讀生，經曆了一年的摸滾，現在已經在工作室裡邊準備開發背景項目啦。 不過這篇文章呢，還是想跟大家聊一聊資料結構與算法，學校也是大二上才開設了資料結構這門課，希望可以一邊學習資料結構一邊積累背景項目開發經驗。 最近我們進入了排序算法專題，上節課聊到了"簡單"插入排序，那在簡單的基礎上，我們可以怎麼做進一步的優化呢，這篇來看看優化版--希爾排序！
希爾排序(Shell Sort)是插入排序的一種，它是針對直接插入排序算法的改進。 希爾排序又稱縮小增量排序，因 DL.hell 于 1959 年提出而得名。 它通過比較相距一定間隔的元素來進行，各趟比較所用的距離随着算法的進行而減小，直到隻比較相鄰元素的最後一趟排序為止。
分割待排序記錄的個數，分别進行插入排序
希爾排序是把記錄按下标的一定增量分組，對每組使用直接插入排序算法排序；随着增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個數組恰被分成一組，算法便終止
由于開始時每組隻有很少整數，是以排序很快。之後每組含有的整數越來越多，但是由于這些數也越來越有序，是以排序速度也很快。
初始化gap為length/2，逐漸減小為gap/2，直到gap不滿足>0的條件
拿圖中的第三步舉例，數組分成了兩組[3，1，0，9，7]，[5，6，8，4，2]
對[3，1，0，9，7]進行簡單插入排序，看成前n-1個為有序數組，第n個為待插入的元素(找到自己的位置後插入即可)
不夠清晰的話也可以看下邊這張
力扣912排序數組 : https://leetcode-cn。com/problems/sort-an-array/submissions/ 又是這道題hhh,萬能
我們要先初始化增量gap=length/2，然後不斷縮小gap=gap/2 直到不滿足gap>0
是以我們最外層會需要一個for循環來調控這個gap的變化
對于分組後，由于我們是要對分組後的每一組進行簡單插入排序，而插入排序我們預設從待排序數組的第二位開始，是以我們需要從每一組的第二位開始去周遊，直到整個數組的末尾
for循環讓i=gap;i<數組;i++即可
注意不是跟前一個進行比較了，而是跟 j-gap 比較
for的話，我是先把j指派等于i-gap，這樣的話就是跟j去比較，最後也還會去j-=gap 會導緻我最後跳出循環的時候，得插到j+gap
先去判斷是否 j-gap>=0，滿足才進循環，才會去j-=gap，是以最後j就是要插入的位置
希爾排序沒有辦法用到哨兵了,我們需要注意判斷是否走到頭了
菜鳥教程
尚矽谷資料結構與算法