為什么希爾排序時間復雜度較小？

可以用逆序數來理解，假設我們要從小到大排序，一個數組中取兩個元素如果前面比后面大，則為一個逆序，容易看出排序的本質就是消除逆序數，可以證明對于隨機數組，逆序數是O(N^2)的，而如果采用“交換相鄰元素”的辦法來消除逆序，每次正好只消除一個，因此必須執行O(N^2)的交換次數，這就是為什么冒泡、插入等算法只能到平方級別的原因，反過來，基于交換元素的排序要想突破這個下界，必須執行一些比較，交換相隔比較遠的元素，使得一次交換能消除一個以上的逆序，希爾、快排、堆排等等算法都是交換比較遠的元素，只不過規則各不同罷了。