当前位置:

首页 > 编程开发 > Python实现归并排序的方法

Python实现归并排序的方法

算法描述本节中的第一种高级排序算法是归并排序。“归并”一词,意为“合并”。顾名思义,归并排序算法就是一个先把数列拆分为子数列,对子数列进行排序后,再把有序的子数列合并为完整的有序数列的算法。它实际上采用了分治的思想。归并排序的平均时间复杂度是O(nlgn),最好情况下的时间复杂度是O(nlgn),最坏情况下的时间复杂度也是O(nlgn)。它的空间复杂度是O(1)。另外,归并排序还是一个稳定的排序算法。以升序排序为例,归并算法的流程如图2-21所示。原始数组是一个有8个数的无序数组。一次操作后,把8个数的数

本文目录

    算法描述

    本节中的第一种高级排序算法是归并排序。“归并”一词,意为“合并”。顾名思义,归并排序算法就是一个先把数列拆分为子数列,对子数列进行排序后,再把有序的子数列合并为完整的有序数列的算法。它实际上采用了分治的思想。

    归并排序的平均时间复杂度是O(nlgn),最好情况下的时间复杂度是O(nlgn),最坏情况下的时间复杂度也是O(nlgn)。它的空间复杂度是O(1)。另外,归并排序还是一个稳定的排序算法。

    以升序排序为例,归并算法的流程如图2-21所示。

    原始数组是一个有8个数的无序数组。一次操作后,把8个数的数组分成两个4个数组成的无序数组。接下来的每次操作都是把无序数组不停分成两半,直到每个最小的数组里都只有一个元素为止。当数组里只有一个元素时,这个数组必定是有序的。然后,程序开始把小的有序数组每两个合并成为大的有序数组。先是从两个1个数的数组合并成2个数的数组,再到4个数然后8个数。这时,所有的有序数组全部合并完成,最后产生的最长的有序数组就排序完成了。

    Python实现归并排序的方法

    代码实现

    归并排序代码:

      #归并排序
    nums = [5,3,6,4,1,2,8,7]
    def MergeSort(num):
      if(len(num)<=1):        #递归边界条件
       return num         #到达边界时返回当前的子数组
      mid = int(len(num)/2)      #求出数组的中位数
      llist,rlist = MergeSort(num[:mid]),MergeSort(num[mid:])#调用函数分别为左右数组排序
      result = []
      i,j = 0,0
      while i < len(llist) and j < len(rlist): #while循环用于合并两个有序数组
       if rlist[j]

    运行程序,输出结果为:

    [1,2,3,4,5,6,7,8]

    在MergeSort()函数中,首先进行的是边界条件判断。当传入函数的数组长度只有1时,每一个数独立存在于一个数组中,因此数组已经被分到最小。这时候,递归分解数组的任务已经完成,只需要把分解后的数组返回到上一层递归就可以了。

    如果未排序数组的长度仍然大于1,那么使用变量mid来存储数组最中间的下标,把未排序数组分成左右两个子数组。然后,新建两个数组,用于存储排好序的左右子数组。这里使用了递归的思想。我们只把MergeSort()函数视为一个为列表排序的函数,尽管在MergeSort()函数内部,也可以调用函数本身对两个子数组进行排序。

    随后,使用while循环合并两个已经有序的数组。由于不能确定两个数组中元素的相对大小,所以我们采用i和j两个变量分别标记在左子数组和右子数组中等待加入的元素的位置。当while循环结束时,可能一个子数组的末尾还剩余一些最大的元素没有被添加到result列表中,所以result+=llist[i:]+rlist[j:]语句是为了防止漏掉这些元素。数组合并完成后,函数输出有序数组。

    本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系bd@zhengruan.com
    作者最新文章
    编程开发 Python
    相关文章 更多
    python删除一个列表里的重复元素的方法与代码示例
    python删除一个列表里的重复元素的方法与代码示例

    学习如何使用Python高效删除列表中的重复元素。本文提供5种常见方法的代码示例,涵盖保持顺序与不保持顺序的场景,适合初学者和进阶开发者参考。

    Python写接口的步骤及完整代码示例
    Python写接口的步骤及完整代码示例

    详细讲解使用Python编写Web接口的核心步骤与完整代码示例,涵盖环境准备、路由定义、数据校验、服务启动及调试测试方法。

    codex怎么读取word文档及docx文件操作教程
    codex怎么读取word文档及docx文件操作教程

    介绍如何利用编程工具读取和解析Word文档(docx格式),涵盖基础文本提取代码示例、结构化数据处理逻辑,以及处理复杂排版时的技术局限与替代方案。

    怎么在Python中调用C语言代码提升性能
    怎么在Python中调用C语言代码提升性能

    详细讲解在Python中调用C语言代码提升性能的完整实践指南,包含原理分析、编译步骤、ctypes与CFFI具体实现、性能对比及常见陷阱。

    Python与C语言的性能差异及底层原理
    Python与C语言的性能差异及底层原理

    深入解析Python与C语言在执行效率上的数量级差异,从编译机制、变量内存布局、动态类型推断到GIL锁,系统阐明底层核心原理。

    Python和C语言哪个更适合编程入门
    Python和C语言哪个更适合编程入门

    客观对比Python与C语言在心智负担、底层机制与学习反馈上的核心差异,提供清晰有据的选择标准与切实的入门学习路径。

    selenium上传文件教程本地文件路径设置方法
    selenium上传文件教程本地文件路径设置方法

    深入解析Selenium处理文件上传的技术细节,涵盖标准HTML控件的路径直接注入法与非标准控件的系统级模拟方案,提供Windows与Linux环境下的路径设置最佳实践及常见异常排查。

    大数据开发语言选型:Java对比Scala与Python的优缺点及适用场景
    大数据开发语言选型:Java对比Scala与Python的优缺点及适用场景

    针对大数据工程场景,系统对比Java、Scala与Python在执行性能、生态结合、开发效率和维护成本上的核心差异,给出清晰的架构选型依据与落地方案。

    langgraph python guide中文入门教程详解
    langgraph python guide中文入门教程详解

    本篇LangGraph Python中文入门教程详解,系统梳理StateGraph状态机定义、节点编写、边与条件路由、检查点持久化(MemorySaver)等核心机制,提供从环境安装到完整循环智能体构建的代码示例与实操指导。

    Windows 安装 Python:从官方入口到虚拟环境的可复现实践
    Windows 安装 Python:从官方入口到虚拟环境的可复现实践

    面向后端开发者,基于 Python 官方文档说明如何在 Windows 上安装 Python、创建 venv 虚拟环境及使用 pip 管理依赖。包含可复制命令、验证方法及工具选择边界,避免常见配置误区。

    查看更多
    精品专题 更多
    装机必备
    装机必备

    正软商城装机必备专区,精选办公、浏览器、安全防护、影音播放、压缩解压、设计创作和系统工具等电脑常用正版软件,帮助用户快速完成新电脑软件配置。

    Windows
    Windows

    正软商城Windows软件专区,汇集适用于Windows电脑的办公、设计、安全防护、影音播放、开发工具和系统优化软件,提供软件介绍、系统要求、正版授权及购买下载服务。

    PDF教程
    PDF教程

    正软商城PDF教程频道提供PDF编辑、转换、合并、拆分、压缩及格式处理方法,同时介绍常用PDF软件和工具的使用技巧。

    Mac软件 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    Aperty macOS版
    Aperty macOS版
    macOS

    Aperty 是 Skylum 推出的 AI 人像修图软件,支持自然肤质修饰、瑕疵处理、面部与身体调整、预设及批量同步。

    WINDOWS 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    PixTV 网页版
    PixTV 网页版
    Windows

    PixTV 是一款在浏览器中使用的 AI 视觉内容创作平台,提供图片、视频、音频、文字生成、AI 分镜、局部重绘、提示词反推和无限画布等工具,适合短剧、漫剧、广告及社交媒体内容制作。