ID_first 2022-05-30 18:53 采纳率: 100%
浏览 117
已结题

三路归并得到递增序列(python语言)

#python初学者,在学数据结构,求大家指教以下问题
#有3个递增有序序列L0,1,2,其中元素均为整数,最大元素不超过1000。编写一个实验程序采用三路归并得到递增有序序列L,L包含全部元素。要求:分别采用顺序存储结构和链式存储结构两种存储结构实现
书上只能学到二路归并的做法,三路归并我加了列表上去做不动程序,希望有人可以指导一下

  • 写回答

2条回答 默认 最新

  • 歇歇 2022-06-06 00:54
    关注

    归并排序的过程是:

    1.将一个序列从中间位置分成两个序列。

    2.再将这两个子序列按照第一步继续二分下去。

    3.直到所有的子序列的长度都为1,即不可再二分为止。

    4.最后再将所有的子序列两两归并成一个有序序列即可。

    归并排序主要使用了分治法的思想。

    分治法:将一个规模为n的问题分解为k个规模较小的子问题,这些子问题相互独立且与原问题相同。递归的解决这些子问题,然后将各个子问题的解合并得到原问题的解。

    python代码:

    
    ```python
    #列表归并
    def Merge(a,b):
        #用来存放归并后的列表
        c=[]
        #用来记录列表a已归并的长度
        h=0
        #用来记录列表b已归并的长度
        j=0
        #当h和j的长度都小于待归并的列表a和b的长度时,执行归并循环
        while h<len(a) and j<len(b):
            #如果列表a的开头数字比b的小
            if a[h]<b[j]:
                #则将列表a的开头数字添加到归并列表c中
                c.append(a[h])
                #同时a已归并的长度+1
                h=h+1
            else:
                #反之,则将列表b的开头数字添加到归并列表c中
                c.append(b[j])
                #同时b已归并的长度+1
                j=j+1
        #如果h等于列表a的长度,则意味着列表a已经归并完成
        if h==len(a):
            #将列表b剩下的值依次插入列表c中
            for i in b[j:]:
                c.append(i)
        else:
            #反之,则意味着列表b已经归并完成
            #将列表a剩下的值依次插入列表c中
            for i in a[h:]:
                c.append(i)
        #返回已经归并完成的列表c
        return c
     
     
    #归并排序
    def Merge_Sort(unsorted_list):
        #如果需要归并的列表长度为1,则不需要归并,直接返回列表
        if len(unsorted_list)==1:
            return unsorted_list
        #将待排序列表从中间一分为二,递归进行进行归并排序
        middle=len(unsorted_list)//2
        #待归并列表的左半边
        left=Merge_Sort(unsorted_list[:middle])
        #待归并列表的右半边
        right=Merge_Sort(unsorted_list[middle:])
        #返回左右两边的列表归并
        return Merge(left,right)
     
     
    
    

    ```

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 6月16日
  • 已采纳回答 6月8日
  • 修改了问题 6月2日
  • 赞助了问题酬金5元 6月1日
  • 展开全部

悬赏问题

  • ¥15 pyqt5 中python如何通过Qtwebchannel主动发消息给web前端
  • ¥15 关于HTML中title获取xml内容的问题
  • ¥15 fanuc机器人PRIO083数字信号未复原错误,如何解决?
  • ¥20 如何为现有电路板增加远程控制功能
  • ¥15 C#点击按钮的时候的循环次数就是最后一次,如何是循环第几次的值?
  • ¥15 UE5打包失败,求解决
  • ¥15 请问STM32G431的CANOPEN协议函数怎么写
  • ¥15 graphpad prism 三因素重复测定报错
  • ¥15 openbmc ast2500如何修改MCR04寄存器使用ddr4
  • ¥15 关于#LTC#的问题,如何解决?(相关搜索:示波器)