希爾排序算法

不需要大量的輔助空間，和歸併排序一樣容易實現。 希爾排序是基於插入排序的一種算法， 希爾排序的時間複雜度為

不需要大量的輔助空間，和歸併排序一樣容易實現。希爾排序是基於插入排序的一種算法， 在此算法基礎之上增加了一個新的特性，提高了效率。希爾排序的時間複雜度為 O(N*(logN)2)， 沒有快速排序算法快 O(N*(logN))，因此中等大小規模表現良好，對規模非常大的數據排序不是 最優選擇。但是比O(N2）複雜度的算法快得多。並且希爾排序非常容易實現，算法代碼短而簡單。 此外，希爾算法在最壞的情況下和平均情況下執行效率相差不是很多，與此同時快速排序在最壞 的情況下執行的效率會非常差。 專家門提倡，幾乎任何排序工作在開始時都可以用希爾排序，若在實際使用中證明它不夠快， 再改成快速排序這樣更高級的排序算法. 本質上講，希爾排序算法的一種改進，減少了其複製的次數，速度要快很多。 原因是，當N值很大時數據項每一趟排序需要的個數很少，但數據項的距離很長。 當N值減小時每一趟需要和動的數據增多，此時已經接近於它們排序後的最終位置。 正是這兩種情況的結合才使希爾排序效率比插入排序高很多。