上篇文章我们学习了算法入门——堆排序，这篇文章我们学习算法入门——归并排序、希尔排序。
归并排序
归并排序是将一个数组分解为很多份，直到一份只要一个元素，根据大小排好序并逐步合并起来，如下图所示：
其合并过程如下：
首先3比1大，那么1插入到空列表中，如下图所示：
接下来3比5小，那么3插入到空列表中，如下图所示：
接下来4比5小，那么4插入到空列表中，如下图所示：
这样下来，左边部分的元素已经没有了，剩下右边的元素，那么右边的元素可以全部插入到列表中，如下图所示：
这样就成功把列表排好序了。
示例代码如下：
def merge(li,low,mid,high):
i=low # 首位下标
j=mid+1 # 拆分位置的下标
ltmp=[] # 创建空列表
while i<=mid and j<=high: # 只要左右两边都有数
if li[i]<li[j]: # 当左边元素小于右边的元素时
ltmp.append(li[i]) # 插入左边的元素到ltmp列表
i+=1 # 比较下一个元素
else:
ltmp.append(li[j]) # 当左边元素大于右边的元素时，插入右边的元素到ltmp列表
j+=1
# while执行完，肯定有一部分没数了
while i <=mid: # 当右边没元素时
ltmp.append(li[i]) # 将左边的元素都放在ltmp列表中
i+=1 # 指向下一个元素
while j<=high: # 当左边没元素时
ltmp.append(li[j]) # 将右边的元素都放在ltmp列表中
j+=1
li[low:high+1]=ltmp # 将ltmp列表中的元素都放在li列表中
def merge_sort(li,low,high):
if low<high: # 至少有两个元素
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)
运行结果如下图所示：
希尔排序
希尔排序是一种分组插入排序算法，先把列表以d步长分为若干组，通过插入排序来比较大小使每组元素排好序，再以d/2为步长分若干组，通过插入排序来比较大小使每组元素排好序，这样反复直到d=1，这样就完成了排序。如下图所示：
接下来以d/2分组进行下一趟排序，如下图所示：
最后一趟时d=1，如下图所示：
希尔排序每一趟排序并不使某些元素有序，而是使整体数据越来越接近有序，最后一趟排序使得所有数据有序。
示例代码如下：
def insert_sort(li,gap):
for i in range(gap,len(li)): #
tmp=li[i] # 列表下标为i的元素
j=i-gap # 列表下标为i-gap元素
while j>=0 and li[j]>tmp: # 当左边的大于右边时
li[j+gap]=li[j] # 大的元素放在右边
j-=gap # 指向下一个元素
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)
运行结果如下图所示：
好了，算法入门——归并排序、希尔排序就学到这里，下篇文章学习算法入门的其他知识。
公众号：白巧克力LIN
该公众号发布Python、数据库、Linux、Flask、自动化测试、Git、算法等相关文章！
