归并排序

归并排序是将一个数组分解为很多份，直到一份只要一个元素，根据大小排好序并逐步合并起来，如下图所示：

其合并过程如下：

首先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)

运行结果如下图所示：