希爾排序
希爾排序(Shell Sort)是插入排序的一種。也稱(chēng)縮小增量排序，是直接插入排序算法的一種更高效的改進(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)行排序吵血。
取一個(gè)間隔稱(chēng)為gap，在這個(gè)間隔步長(zhǎng)取值分為幾組元素偷溺，分別插入排序蹋辅，最后步長(zhǎng)為1的時(shí)候插入排序。
最核心部分還是插入排序挫掏。
代碼實(shí)現(xiàn)：
# coding:utf-8
def shell_sort(alist):
"""希爾排序"""
# n=9
n = len(alist)
# i=4
gap = n // 2
# i = 1
# gap變化到0之前侦另，插入算法執(zhí)行的次數(shù)
while gap >= 1:
# 插入算法，與普通插入算法的區(qū)別就是gap步長(zhǎng)
for j in range(gap, n):
i = j
while i > 0:
if alist[i] < alist[i - gap]:
[alist[i], alist[i - gap]] = alist[i - gap], alist[i]
i -= gap
else:
break
gap //= 2
if __name__ == "__main__":
li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(li)
shell_sort(li)
print(li)
結(jié)果：
希爾排序結(jié)果
