希爾排序(Shell Sort)是插入排序的一種剧防。也稱縮小增量排序帖族，是直接插入排序算法的一種更高效的改進(jìn)版本范舀。希爾排序是非穩(wěn)定排序算法爹凹。該方法因DL．Shell于1959年提出而得名南誊。 希爾排序是把記錄按下標(biāo)的一定增量分組身诺，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少抄囚，每組包含的關(guān)鍵詞越來(lái)越多霉赡，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組幔托，算法便終止穴亏。
希爾排序過(guò)程
希爾排序的基本思想是：將數(shù)組列在一個(gè)表中并對(duì)列分別進(jìn)行插入排序，重復(fù)這過(guò)程重挑，不過(guò)每次用更長(zhǎng)的列（步長(zhǎng)更長(zhǎng)了嗓化，列數(shù)更少了）來(lái)進(jìn)行。最后整個(gè)表就只有一列了谬哀。將數(shù)組轉(zhuǎn)換至表是為了更好地理解這算法刺覆，算法本身還是使用數(shù)組進(jìn)行排序。
例如史煎，假設(shè)有這樣一組數(shù)[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]谦屑，如果我們以步長(zhǎng)為5開(kāi)始進(jìn)行排序，我們可以通過(guò)將這列表放在有5列的表中來(lái)更好地描述算法篇梭，這樣他們就應(yīng)該看起來(lái)是這樣(豎著的元素是步長(zhǎng)組成)：
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后我們對(duì)每列進(jìn)行排序：
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
將上述四行數(shù)字氢橙，依序接在一起時(shí)我們得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。這時(shí)10已經(jīng)移至正確位置了恬偷，然后再以3為步長(zhǎng)進(jìn)行排序：
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后變?yōu)椋?br>
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以1步長(zhǎng)進(jìn)行排序（此時(shí)就是簡(jiǎn)單的插入排序了）
希爾排序的分析
def shell_sort(alist):
n = len(alist)
# 初始步長(zhǎng)
gap = n / 2
while gap > 0:
# 按步長(zhǎng)進(jìn)行插入排序
for i in range(gap, n):
j = i
# 插入排序
while j>=gap and alist[j-gap] > alist[j]:
alist[j-gap], alist[j] = alist[j], alist[j-gap]
j -= gap
# 得到新的步長(zhǎng)
gap = gap / 2
alist = [54,26,93,17,77,31,44,55,20]
shell_sort(alist)
print(alist)
時(shí)間復(fù)雜度
最優(yōu)時(shí)間復(fù)雜度：根據(jù)步長(zhǎng)序列的不同而不同
最壞時(shí)間復(fù)雜度：O(n2)
穩(wěn)定想：不穩(wěn)定
希爾排序演示
