算法學習：希爾排序（插入排序）
1、插入排序有兩種，直接插入排序和希爾排序
2、希爾排序核心思想
希爾排序本質也是一種插入排序，但是是根據簡單插入排序進行優(yōu)化有的一種更加高效的版本，別稱是縮小增量排序。
希爾排序的核心思想是將排序數組按照增量進行分組，然后對分組的元素進行直接插入排序，循環(huán)縮小分組增量，最后當增量長度為1是排序結束。
3、舉例：給不同身高的人進行排序
第一步：分組，找一個間隔分組，間隔取4。間隔通常是總長度的一半，奇數偶數均可。
如圖所示：0,4,8一組；1,5一組，2,6一組；3,7一組。
第二步：對于每組元素，分別進行排序
第一組：0,4,8 已經排好序；
第二組：5,1
第三組：6,2
第四種：3,7
所有組拍完序后，此時：
第三步：繼續(xù)設置間隔，這次的間隔是上次的一半，間隔取2
第一組：0,2,4,6,8
第二組：1,3,5,7
第四步：重復步驟二給每組排序：
第一組：2,0,6,4,8
第二組：3,7,1,5
全部排完序后：
第五步：再次設置間隔，間隔取上次的一半1
當間隔為1時，使用插入排序法，進行排序
最終結果：
方法總結：對每個分組進行插入排序
4、代碼
對數組[83,29,30,5,99,34,12,66]使用希爾排序進行排序。
# 代碼1
def shellsort(arr):
#設置步長
gap = len(arr)
while gap > 0:
#遍歷分組
for i in range(gap,len(arr)):
#對當前分組的元素進行插入排序
for j in range(i,gap-1,-gap):
if arr[j] < arr[j-gap]:
arr[j],arr[j-gap]=arr[j-gap],arr[j]
else:
break
print(arr)
gap //= 2# 步長減半
return arr
arr=[83,29,30,5,99,34,12,66]
print("最終結果：",shellsort(arr))
結果：
#代碼2：分成直接插入排序+希爾排序思想
def compare(arr,i,gap): #直接插入排序 j = i-gap while j>=0: if arr[j]>arr[j+gap]: arr[j+gap],arr[j]=arr[j],arr[j+gap] j-=gap else: break def shellSort(arr): gap=len(arr)//2 while gap>=1:#步長大于0的時候，都要做以下步驟 #1 分組 #2 對分組的元素進行直接插入排序 #3 縮小步長 for i in range(gap):#對每組都要進行直接插入排序 for j in range(i,len(arr),gap): compare(arr,j,gap) gap//=2 #一輪循環(huán)之后，才調整步長 return arr arr=[7,3,45,23,-1,34,88,9,4] print(shellSort(arr)) #結果[-1, 3, 4, 7, 9, 23, 34, 45, 88]
5、希爾排序的時間復雜度
希爾排序是按照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，所以插入排序的元素個素很少，速度很快；
當元素基本有序了，步長很小，插入排序對于有序的序列效率很高。
所以希爾排序的時間復雜度比O(n^2)要好一些。
浙公網安備 33010602011771號