美文网首页算法
算法入门——归并排序、希尔排序

算法入门——归并排序、希尔排序

作者: 白巧克力LIN | 来源:发表于2022-08-22 21:49 被阅读0次

上篇文章我们学习了算法入门——堆排序,这篇文章我们学习算法入门——归并排序、希尔排序。

归并排序

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



其合并过程如下:

首先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、算法等相关文章!

相关文章

网友评论

    本文标题:算法入门——归并排序、希尔排序

    本文链接:https://www.haomeiwen.com/subject/jwcwgrtx.html