什么是希爾排序

希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。

該方法因DL.Shell于1959年提出而得名。希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序：隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。

算法步驟：
① 選擇一個增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
② 按增量序列個數 k，對序列進行 k 趟排序；
③ 每趟排序，根據對應的增量 ti，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序。僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

---

希爾排序過程

希爾排序的基本思想是∶將數組列在一個表中并對列分別進行插入排序，重復這過程，不過每次用更長的列（步長更長了，列數更少了）來進行。最后整個表就只有一列了。將數組轉換至表是為了更好地理解這算法，算法本身還是使用數組進行排序。

例如，假設有這樣一組數

[13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10]

如果我們以步長為5開始進行排序，我們可以通過將這列表放在有5列的表中來更好地描述算法，這樣他們就應該看起來是這樣（堅著的元素是步長組成）:

13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10

然后我們對每列進行排序：

10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45

將上述四行數字，依序接在一起時我們得到：

[10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45]

這時10已經移至正確位置了，然后再以3為步長進行排序:

10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45

排序之后變為∶

10 14 13 25 23 33 27 25 59 39 65 73 45 94 82 94

最后以1步長進行排序（此時就是簡單的插入排序了)

---

希爾排序的演示

---

時間復雜度

• 最優時間復雜度：根據步長序列的不同而不同
• 最壞時間復雜度：O(n^2)
• 穩定想：不穩定

---

代碼實現

def shell_sort(alist):'''希爾排序'''n = len(alist)gap = n//2#gap變化到0之前，插入算法執行的次數#插入算法,與普通的插入算法的區別就是gap步長while gap > 0:for j in range(gap,n):i = jwhile i > 0:if alist[i] < alist[i-gap]:alist[i],alist[i-gap] = alist[i-gap],alist[i]i -= gapelse:break#縮短gap步長gap//=2if __name__ == '__main__':li = [13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10]print(li)shell_sort(li)print(li)

結果：

[13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10] [10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94]

總結

以上是生活随笔為你收集整理的数据结构与算法笔记（九）—— 希尔排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。