python实现2路归并排序

ops/2024/11/15 4:56:10/

       归并排序是通过序列的合并来实现排序的。

       对于一个序列a1 a2 a2 … an,我们可以首先把它们看成一系列的只有一个元素的有序子序列a1;a2;a3;…;an,我们让a1和a2合并,a3和a4合并,依次类推,最后得到一个有序子序列的序列a1 a2;a3 a4;a5 a6;…;an-1 an,接下来让a1 a2和a3 a4合并,a5 a6和a7 a8合并,以此类推,得到一个更大有序子序列的序列a1 a2 a3 a4;a5 a6 a7 a8;…;an-3 an-2 an-1 an,按照同样的逻辑继续合并,直至最后得到唯一一个序列,它就是排好序的结果序列。   

       算法实现的难点和需要注意的地方在于边界情形,子序列两两配对的时候,可能最后有一个子序列落单了,找不到另一个子序列了,还有两个子序列进行合并时,我们交替得把两个序列的切片首尾接在一起,要注意对最后一个切片的处理。    

       下面是代码:

python">def mergesort(source):dest = [0] * len(source)endpos = len(source)rsize = 1while rsize < len(source):lpos, rpos, pos = 0, rsize, 0lendpos, rendpos = rsize, min(rpos + rsize, endpos)while lpos < endpos and rpos < endpos:while lpos < lendpos and rpos < rendpos:if source[lpos] <= source[rpos]:dest[pos] = source[lpos]lpos += 1else:dest[pos] = source[rpos]rpos += 1pos += 1if lpos < lendpos:dest[pos:pos + (lendpos - lpos)] = source[lpos:lendpos]pos += lendpos - lposlpos = lendposif rpos < rendpos:dest[pos:pos + (rendpos - rpos)] = source[rpos:rendpos]pos += rendpos - rposrpos = rendposlpos, rpos = rendpos, min(rendpos + rsize, endpos)lendpos, rendpos = min(lpos + rsize, endpos), min(rpos + rsize, endpos)if lpos < endpos:dest[pos:] = source[lpos:]rsize *= 2source, dest = dest, sourcereturn sourceprint(mergesort([2, 1, 4, 3, 5, 6, 3, 1,0]))


http://www.ppmy.cn/ops/31688.html

相关文章

eNSP-抓包解析HTTP、FTP、DNS协议

一、环境搭建 1.http服务器搭建 2.FTP服务器搭建 3.DNS服务器搭建 二、抓包 三、http协议 1.HTTP协议&#xff0c;建立在TCP协议之上 2.http请求 3.http响应 请求响应报文参考&#xff1a;https://it-chengzi.blog.csdn.net/article/details/113809803 4.浏览器开发者工具抓包…

简化Transformer模型,以更少的参数实现更快的训练速度

在深度学习领域&#xff0c;Transformer模型因其卓越的性能而广受欢迎&#xff0c;但其复杂的架构也带来了训练时间长和参数数量多的挑战。ETH Zurich的研究人员Bobby He和Thomas Hofmann在最新研究中提出了一种简化的Transformer模型&#xff0c;通过移除一些非必要的组件&…

华为试题之删除最少字符

题目描述 删除字符串中出现次数最少的字符 如果多个字符出现次数一样则都删除 输入描述 输入只包含小写字母 输出描述 输出删除后剩余的字符 若删除后字符串长度为0&#xff0c;则输出empty 我的思路是将字符串中的字符对应的数量和key统计后放到对应的字典中&#xff0c; 对字…

Docker - 修改服务的端口

1. 测试 新建一个httpd服务 docker run -itd -p 1314:80 --name test -h test httpd 2. 先停止容器和 docke r服务 docker stop test #停止容器3. 修改配置 cd /var/lib/docker/containers ls 找到需要修改的 cd 1fc55f0d24014217cff68c9a417ca46cf50312caa5c9e6bb24085126…

蓝桥杯国赛备赛复习——数据结构

一、链表 1.1 单链表 package 链表;public class 单链表 {static int e[] new int[11010]; // index号节点的value值&#xff08;value&#xff09;static int ne[] new int[11010];// index号节点的下一个节点的index&#xff08;nextNode&#xff09;static int head-1,i…

windows ubuntu sed,awk,grep篇,8,Awk 语法和基础命令

目录 51.Awk 命令语法 52.Awk 程序结构(BEGIN,body,END)区域 53.打印命令 54.模式匹配 Awk 是一个维护和处理文本数据文件的强大语言。在文本数据有一定的格式&#xff0c;即每行数据包 含多个以分界符分隔的字段时&#xff0c;显得尤其有用。即便是输入文件没有一定的格式&a…

深入探索Element-UI:构建高效Web前端的利器

深入探索Element-UI&#xff1a;构建高效Web前端的利器 引言&#xff1a;前端框架的选择与Element-UI的定位一、Element-UI初探二、快速上手&#xff1a;安装与配置三、核心组件深度解析四、实用功能与进阶技巧五、性能优化与最佳实践六、实战案例分析七、与其他技术栈的集成 安…

vue3 jspdf,element table 导出excel、pdf,横板竖版分页

多个表格需要&#xff0c;pdf需要的格式与原本展示的表格样式不同 1.创建一个新的表格&#xff0c;设置pdf需要的样式&#xff0c;用vue的h函数放入dom中 2.excel用xlxs插件直接传入新建el-table的dom,直接导出 3.pdf导出类似excel黑色边框白底黑字的文件&#xff0c;把el-t…