我的演算法筆記_排序_希爾排序

希爾排序是一種基於插入排序的快速的排序演算法。希爾排序為了加快速度，改進了插入排序，交換不相鄰的元素以對數組的局部進行排序，並最終用插入排序將局部有序的數組排序。

希爾排序的思想是使數組中任意間隔為h的元素都是有序的（h有序數組）。

它的一種實現方法是，對於每個h，用插入排序將h個子數組獨立地排序。即將插入排序中移動元素的距離由1改為h即可，其實現就轉化為了一盒類似於插入排序但使用不同增量的過程。

所以我們在插入排序演算法中加入一個外循環將h按照遞增序列遞減，我們就可以得到一個簡潔的希爾排序演算法。

希爾演算法的性能與h的遞增序列有很大的關係。

相比於插入排序來說，數組越大，希爾排序的優勢越大。

關於希爾排序的性能，目前最重要的結論是它的運行時間達不到平方級別。已知在最壞的情況下其比較次數和成正比，突破了平方級別的運行時間屏障。因此，對於中等大小的數組它的運行時間是可以接受的。