排序算法之希爾排序
整理自B站真情的可貴課程內(nèi)容~
1.希爾排序定義：
是直接插入排序的一種更高效的改進版本。希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分為一組，算法便終止。希爾排序又稱“縮小增量排序”，即每趟只對相同增量距離的關鍵字進行比較，這與關鍵字序列初始有序或無序無關。
2.時間復雜度：
最優(yōu)時間復雜度：根據(jù)步長來定
最差時間復雜度：O(n2)
3.穩(wěn)定性：不穩(wěn)定
4.Python代碼：
此處gap的選取采用半折的方法，僅僅是熟悉希爾排序，具體問題中gap的選取很復雜，依據(jù)具體問題來定。
1 #coding:utf-8 2 #希爾排序 3 def shell_sort(alist): 4 """插入排序""" 5 n = len(alist) 6 gap = n // 2 7 #gap變化到0之前，插入算法執(zhí)行的次數(shù) 8 while gap > 0: #gap最終降為1時即普通的插入排序 9 #插入算法，與普通的插入算法的區(qū)別就是gap步長 10 for j in range(gap,n): 11 i = j 12 while i > 0: 13 if alist[i] < alist[i - gap]: 14 alist[i],alist[i-gap] = alist[i-gap],alist[i] 15 i -= gap 16 else: 17 break 18 #縮短gap步長 19 gap //= 2 20 21 if __name__ == "__main__": 22 alist = [93, 54, 77, 31, 44, 55, 226] 23 print("希爾排序之前的原始列表：") 24 print(alist) 25 shell_sort(alist) 26 print("希爾排序之后的列表：") 27 print(alist)
輸出結果：
浙公網(wǎng)安備 33010602011771號