直接插入排序在時間複雜度上優勢不明顯。達到o(n2)的水準了，是以需要想辦法降低時間複雜度是很有必要的。當記錄的排序就是所求的排序時，時間複雜度會大幅下降，為o(n)。這是最理想的狀态，當順序剛好是逆序的時候，時間複雜度最大為o(n2)。是以記錄越是有序，時間複雜度越低。這個和快速排序不同，大家都知道快速排序在有序的情況下效果是很差的吧。
現在的問題是，如何使得記錄變得有序，這個也是我們求的最後結果。希爾排序是一種很好的選擇，它的原理是使得記錄大體上有序，雖然不是所有都有序，但是大體上有序也是很加快排序速度的。希爾排序(shell sort)是插入排序的一種。是針對直接插入排序算法的改進。插入排序的增量是1，而希爾是一個數組決定的。
先取一個小于n的整數dt作為第一個增量，把檔案的全部記錄分成d1個組。所有距離為d1的倍數的記錄放在同一個組中。先在各組内進行直接插入排序；然後，取第二個增量d2<d1重複上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。
是以希爾插入排序和直接插入排序的差別就是增量的差別。
至于dlta[]和t，這決定于你的資料量，不過最後一個dlta[]數組的值，一定要是1，這樣才能保證排序一定正确。
下面給一個完整的例子。
希爾插入排序執行個體
希爾排序在資料量多的時候，對比直接插入排序才能展現它的價值，實驗證明，希爾插入排序的時間複雜度大約為o(n3/2).
相關資料内部排序——直接插入排序 參考資料
[1] 嚴蔚敏 吳偉民 《資料結構(c語言版)》 北京：清華大學出版社，1997.4