希爾排序為什麼會那麼牛那麼快，能夠證明嗎？
01-11
樓主用的是書上說的最原始的那種增量，即從length逐步減半，其實這還不算最快的希爾，有幾個增量在實踐中表現更出色，具體可以看weiss的數據結構書，同時裡面有希爾排序複雜度的證明，但是涉及組合數學和數論，希爾排序是實現簡單但是分析極其困難的一個演算法的例子至於樓主問為啥希爾能突破O(N^2)的界，可以用逆序數來理解，假設我們要從小到大排序，一個數組中取兩個元素如果前面比後面大，則為一個逆序，容易看出排序的本質就是消除逆序數，可以證明對於隨機數組，逆序數是O(N^2)的，而如果採用「交換相鄰元素」的辦法來消除逆序，每次正好只消除一個，因此必須執行O(N^2)的交換次數，這就是為啥冒泡、插入等演算法只能到平方級別的原因，反過來，基於交換元素的排序要想突破這個下界，必須執行一些比較，交換相隔比較遠的元素，使得一次交換能消除一個以上的逆序，希爾、快排、堆排等等演算法都是交換比較遠的元素，只不過規則各不同罷了
Indeed, when the number of inversions is low, insertion sort(as well as shellsort) is likely to be faster than any sorting method.
不談常數說實際運行時間是耍流氓。
還有oj的數據並不代表什麼，可能數據剛好就希爾表現的比快排好。另外還要看你快排的寫法，遞歸還是非遞歸，基準元素選擇以及是否有利於緩存命中balabalaps：順便答點相關的，shell sort在適當的gap sequence下快的原因在於一次消除更多的逆序對以及通過gap減少重複無意義的比較。比如說按4排完後再按2排無疑會有一部分比較是無意義的。因為在按4已經有序了，再按2排序能消除的逆序對就大大減少了。我記得shell sort最好的複雜度大概能到O（n^1.2）到O（n^1.3）的樣子
去看英文wiki吧，有你想要的。快排理論上要比希爾排序快，你自己實現的快排比希爾慢的原因，主要估計還是因為用了函數遞歸的緣故（快排是標準的遞歸演算法，一般用遞歸函數實現）。如果沒對遞歸做優化，那麼遞歸本身的時間開銷可能會超過排序的開銷（因為你的元素比較和交換操作都很簡單）。
大部分情況下，還是快排好一點希爾排序的時間複雜度與增量序列的選取有關，例如希爾增量時間複雜度為O(n2)，而Hibbard增量的希爾排序的時間複雜度為O(
)，希爾排序時間複雜度的下界是n*log2n。
終究沒有干過stl快排
for循環里是插入排序嗎？不是很明白為什麼i++要加到length這種方式，題主能幫我解釋一下你的演算法嗎，謝謝！
在樓上演算法大神之後弱弱問一句，oj開優化了嗎。。。不開優化的STL是殘的。。
shell排序的O（n^2）前的常數因子較快排要小的多，當數據量小時shell 排序表現更好。更何況shell 排序在最壞的情況下和平均情況下執行效率接近，與此同時快排在最壞的情況下執行的效率很低。
推薦閱讀：
