4.希爾排序（縮小增量排序）

4.1 算法思想

希爾排序是插入排序的一種優化，又稱“縮小增量排序”，是直接插入排序算法的一種更高效的改進版本。
希爾排序是把記錄 按下標的一定增量分組 ，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。

先取一個正整數d1 該方法實質上是一種分組插入方法。

4.2 算法分析

希爾排序的時間復雜度與增量序列的選取有關，例如希爾增量時間復雜度為O(n2)，而Hibbard增量的希爾排序的時間復雜度為O( n^(3/2) )，希爾排序時間復雜度的下界是n*log2n。希爾排序沒有快速排序算法快 O(n(logn))，因此中等大小規模表現良好，對規模非常大的數據排序不是最優選擇。

Shell排序的執行時間依賴于增量序列。
好的增量序列的共同特征：
① 最后一個增量必須為1；
② 應該盡量避免序列中的值(尤其是相鄰的值)互為倍數的情況。

這種算法不需要額外的空間，時間復雜度為o(1)

4.3 算法過程

先將整個待排序的元素序列按照增量分割成為若干子序列分別進行直接插入排序，具體算法描述：

1. 選擇一個增量序列t1，t2，…，tk，其中t1>t2>……>tk，tk=1；
2. 按增量序列個數k，對序列進行k 次排序；
3. 每次排序，根據對應的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序。僅增量為1 時，即把所有的元素進行一個插入排序處理，表長度即為整個序列的長度。

4.4 python代碼

            
              
                def
              
              
                shellSort
              
              
                (
              
              numList
              
                )
              
              
                :
              
              
    n 
              
                =
              
              
                len
              
              
                (
              
              numList
              
                )
              
              
                if
              
               n 
              
                ==
              
              
                0
              
              
                or
              
               n 
              
                ==
              
              
                1
              
              
                :
              
              
                return
              
               numList
    gap 
              
                =
              
               n 
              
                //
              
              
                2
              
              
                while
              
               gap 
              
                >=
              
              
                1
              
              
                :
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              gap
              
                ,
              
              n
              
                )
              
              
                :
              
              
                # 把前gap個空出來，以便進行各組之間的插入排序(插入排序也是把第一個元素空出來，當成已經排好序的序列)
              
              
            tempindex 
              
                =
              
               i
            
              
                while
              
               tempindex 
              
                >=
              
               gap 
              
                and
              
               numList
              
                [
              
              tempindex 
              
                -
              
               gap
              
                ]
              
              
                >
              
               numList
              
                [
              
              tempindex
              
                ]
              
              
                :
              
              
                numList
              
                [
              
              i 
              
                -
              
               gap
              
                ]
              
              
                ,
              
               numList
              
                [
              
              tempindex
              
                ]
              
              
                =
              
               numList
              
                [
              
              tempindex
              
                ]
              
              
                ,
              
              numList
              
                [
              
              tempindex 
              
                -
              
               gap
              
                ]
              
              
                tempindex 
              
                -=
              
               gap
                
              
                # 先把一個子序列中的元素排好序，某個子序列中的元素下標之間的間隔為gap
              
              
        gap 
              
                =
              
               gap 
              
                //
              
              
                2
              
              
                return
              
               numList
numlist 
              
                =
              
              
                [
              
              
                4
              
              
                ,
              
              
                5
              
              
                ,
              
              
                7
              
              
                ,
              
              
                8
              
              
                ,
              
              
                6
              
              
                ,
              
              
                1
              
              
                ,
              
              
                2
              
              
                ,
              
              
                3
              
              
                ,
              
              
                4
              
              
                ]
              
              
                print
              
              
                (
              
              shellSort
              
                (
              
              numlist
              
                )
              
              
                )
              
              
                # 輸出結果為：[1, 2, 3, 4, 4, 5, 6, 7, 8]