上篇文章我們學(xué)習(xí)了算法入門——堆排序，這篇文章我們學(xué)習(xí)算法入門——?dú)w并排序、希爾排序。
歸并排序
歸并排序是將一個(gè)數(shù)組分解為很多份，直到一份只要一個(gè)元素，根據(jù)大小排好序并逐步合并起來，如下圖所示：
其合并過程如下：
首先3比1大，那么1插入到空列表中，如下圖所示：
接下來3比5小，那么3插入到空列表中，如下圖所示：
接下來4比5小，那么4插入到空列表中，如下圖所示：
這樣下來，左邊部分的元素已經(jīng)沒有了，剩下右邊的元素，那么右邊的元素可以全部插入到列表中，如下圖所示：
這樣就成功把列表排好序了。
示例代碼如下：
def merge(li,low,mid,high):
i=low # 首位下標(biāo)
j=mid+1 # 拆分位置的下標(biāo)
ltmp=[] # 創(chuàng)建空列表
while i<=mid and j<=high: # 只要左右兩邊都有數(shù)
if li[i]<li[j]: # 當(dāng)左邊元素小于右邊的元素時(shí)
ltmp.append(li[i]) # 插入左邊的元素到ltmp列表
i+=1 # 比較下一個(gè)元素
else:
ltmp.append(li[j]) # 當(dāng)左邊元素大于右邊的元素時(shí)，插入右邊的元素到ltmp列表
j+=1
# while執(zhí)行完，肯定有一部分沒數(shù)了
while i <=mid: # 當(dāng)右邊沒元素時(shí)
ltmp.append(li[i]) # 將左邊的元素都放在ltmp列表中
i+=1 # 指向下一個(gè)元素
while j<=high: # 當(dāng)左邊沒元素時(shí)
ltmp.append(li[j]) # 將右邊的元素都放在ltmp列表中
j+=1
li[low:high+1]=ltmp # 將ltmp列表中的元素都放在li列表中
def merge_sort(li,low,high):
if low<high: # 至少有兩個(gè)元素
mid=(low+high)//2
# 將列表分為左右兩部分
merge_sort(li,low,mid)
merge_sort(li,mid+1,high)
# 逐步合并
merge(li,low,mid,high)
li=[10,9,3,2,5,4,8,7]
merge_sort(li,0,len(li)-1)
print(li)
運(yùn)行結(jié)果如下圖所示：
希爾排序
希爾排序是一種分組插入排序算法，先把列表以d步長(zhǎng)分為若干組，通過插入排序來比較大小使每組元素排好序，再以d/2為步長(zhǎng)分若干組，通過插入排序來比較大小使每組元素排好序，這樣反復(fù)直到d=1，這樣就完成了排序。如下圖所示：
接下來以d/2分組進(jìn)行下一趟排序，如下圖所示：
最后一趟時(shí)d=1，如下圖所示：
希爾排序每一趟排序并不使某些元素有序，而是使整體數(shù)據(jù)越來越接近有序，最后一趟排序使得所有數(shù)據(jù)有序。
示例代碼如下：
def insert_sort(li,gap):
for i in range(gap,len(li)): #
tmp=li[i] # 列表下標(biāo)為i的元素
j=i-gap # 列表下標(biāo)為i-gap元素
while j>=0 and li[j]>tmp: # 當(dāng)左邊的大于右邊時(shí)
li[j+gap]=li[j] # 大的元素放在右邊
j-=gap # 指向下一個(gè)元素
li[j+gap]=tmp
print(f'把列表分{gap}組：',li)
def shell_sort(li):
d=len(li)//2 # 分組
while d>=1:
insert_sort(li,d)
d//=2
li=[2,1,5,9,4,6,0,3]
shell_sort(li)
運(yùn)行結(jié)果如下圖所示：
好了，算法入門——?dú)w并排序、希爾排序就學(xué)到這里，下篇文章學(xué)習(xí)算法入門的其他知識(shí)。
公眾號(hào)：白巧克力LIN
該公眾號(hào)發(fā)布Python、數(shù)據(jù)庫(kù)、Linux、Flask、自動(dòng)化測(cè)試、Git、算法等相關(guān)文章！
