#python初学者,在学数据结构,求大家指教以下问题
#有3个递增有序序列L0,1,2,其中元素均为整数,最大元素不超过1000。编写一个实验程序采用三路归并得到递增有序序列L,L包含全部元素。要求:分别采用顺序存储结构和链式存储结构两种存储结构实现
书上只能学到二路归并的做法,三路归并我加了列表上去做不动程序,希望有人可以指导一下
三路归并得到递增序列(python语言)
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
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
悬赏问题
- ¥15 WPF 大屏看板表格背景图片设置
- ¥15 这个主板怎么能扩出一两个sata口
- ¥15 不是,这到底错哪儿了😭
- ¥15 2020长安杯与连接网探
- ¥15 关于#matlab#的问题:在模糊控制器中选出线路信息,在simulink中根据线路信息生成速度时间目标曲线(初速度为20m/s,15秒后减为0的速度时间图像)我想问线路信息是什么
- ¥15 banner广告展示设置多少时间不怎么会消耗用户价值
- ¥16 mybatis的代理对象无法通过@Autowired装填
- ¥15 可见光定位matlab仿真
- ¥15 arduino 四自由度机械臂
- ¥15 wordpress 产品图片 GIF 没法显示