python排序算法之归并排序怎么实现

PHPz

发布时间：2023-05-21 08:31:36

1282人浏览过

来源于亿速云

转载

算法描述

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

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

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

原始数组是一个有8个数的无序数组。一次操作后，把8个数的数组分成两个4个数组成的无序数组。每个操作都将无序数组分成两半，直至所有最小的子数组仅包含一个元素。当数组里只有一个元素时，这个数组必定是有序的。然后，程序开始把小的有序数组每两个合并成为大的有序数组。首先是将两个包含一个数的数组合并成一个包含两个数的数组，然后再把两个包含两个数的数组合并成一个包含四个数的数组，最后合并成一个包含八个数的数组。当所有有序数组合并完毕时，形成的最长有序数组就完成排序。

python排序算法之归并排序怎么实现

立即学习“Python免费学习笔记（深入）”；

代码实现

归并排序代码：

InsCode

InsCode 是CSDN旗下的一个无需安装的编程、协作和分享社区

下载

  #归并排序
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，那么使用变量mid来存储数组最中间的下标，把未排序数组分成左右两个子数组。然后，新建两个数组，用于存储排好序的左右子数组。这里使用了递归的思想。我们只把MergeSort()函数视为一个为列表排序的函数，尽管在MergeSort()函数内部，也可以调用函数本身对两个子数组进行排序。
随后，使用while循环合并两个已经有序的数组。由于不能确定两个数组中元素的相对大小，所以我们采用i和j两个变量分别标记在左子数组和右子数组中等待加入的元素的位置。当while循环结束时，可能一个子数组的末尾还剩余一些最大的元素没有被添加到result列表中，所以result+=llist[i:]+rlist[j:]语句是为了防止漏掉这些元素。数组合并完成后，函数输出有序数组。

如何在删除嵌套字典中不符合条件的项后重新编号键值

Python 大数据量下的数据结构选择

Python 如何正确设置请求超时？

repr 如何自动折行显示超长对象（pprint 风格）

Python 重构与重写的决策标准

python速学教程(入门到精通)

python怎么学习？python怎么入门？python在哪学？python怎么学才快？不用担心，这里为大家提供了python速学教程(入门到精通)，有需要的小伙伴保存下载就能学习啦！

下载

相关标签:

python

本站声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

上一篇：Python虚拟机中调试器的实现原理是什么下一篇：Python上下文管理器怎么使用

作者最新文章

如何在Spryker项目中实现前端与后端高效通信？Spryker/Zed-Request与Composer助你轻松连接！

2025-09-12 12:40

如何高效生成唯一ID？Ramsey/Uuid助你解决分布式系统中的ID难题

2025-09-13 09:51

Yii2数据库迁移总是手动写？insolita/yii2-migration-generator助你告别繁琐，实现自动化！

2025-09-15 09:38

如何解决复杂系统可视化难题，Spryker/Graphviz助你轻松绘制依赖与状态图

2025-09-15 09:52

如何高效生成订单/发票号？SprykerSequenceNumber模块助你轻松搞定

2025-09-16 10:01

如何解决电商平台商品属性管理混乱的问题，使用SprykerProductAttribute模块助你实现灵活高效的数据管理

2025-09-16 12:23

解锁夸克浏览器AI搜索新功能_掌握夸克AI搜索的进阶玩法

2025-10-13 17:08

升级夸克浏览器体验AI搜索_夸克AI搜索核心功能深度解析

2025-10-28 20:58

微信朋友圈能不能定时发微信朋友圈定时发送辅助工具使用

2026-01-11 08:41

企业微信朋友圈怎么定时发送企业微信定时发布朋友圈教程

2026-01-19 01:11

热门AI工具

DeepSeek

幻方量化公司旗下的开源大模型平台

AI大模型

开放平台

豆包大模型

字节跳动自主研发的一系列大型语言模型

AI大模型

通义千问

阿里巴巴推出的全能AI助手

AI大模型

腾讯元宝

腾讯混元平台推出的AI助手

文档处理

Excel 表格

文心一言

文心一言是百度开发的AI聊天机器人，通过对话可以生成各种形式的内容。

AI大模型

中文写作

讯飞写作

基于讯飞星火大模型的AI写作工具，可以快速生成新闻稿件、品宣文案、工作总结、心得体会等各种文文稿

中文写作

写作工具

即梦AI

一站式AI创作平台，免费AI图片和视频生成。

图片拼接

图画生成

ChatGPT

最最强大的AI聊天机器人程序，ChatGPT不单是聊天机器人，还能进行撰写邮件、视频脚本、文案、翻译、代码等任务。

AI大模型

中文写作

智谱清言 - 免费全能的AI助手

AI大模型

PDF 文档

相关专题

云朵浏览器入口合集

本专题整合了云朵浏览器入口合集，阅读专题下面的文章了解更多详细地址。

2026.01.20

Java JVM 原理与性能调优实战

本专题系统讲解 Java 虚拟机（JVM）的核心工作原理与性能调优方法，包括 JVM 内存结构、对象创建与回收流程、垃圾回收器（Serial、CMS、G1、ZGC）对比分析、常见内存泄漏与性能瓶颈排查，以及 JVM 参数调优与监控工具（jstat、jmap、jvisualvm）的实战使用。通过真实案例，帮助学习者掌握 Java 应用在生产环境中的性能分析与优化能力。

2026.01.20

PS使用蒙版相关教程

本专题整合了ps使用蒙版相关教程，阅读专题下面的文章了解更多详细内容。

2026.01.19

java用途介绍

本专题整合了java用途功能相关介绍，阅读专题下面的文章了解更多详细内容。

2026.01.19

java输出数组相关教程

本专题整合了java输出数组相关教程，阅读专题下面的文章了解更多详细内容。

2026.01.19

java接口相关教程

本专题整合了java接口相关内容，阅读专题下面的文章了解更多详细内容。

2026.01.19

xml格式相关教程

本专题整合了xml格式相关教程汇总，阅读专题下面的文章了解更多详细内容。

2026.01.19

PHP WebSocket 实时通信开发

本专题系统讲解 PHP 在实时通信与长连接场景中的应用实践，涵盖 WebSocket 协议原理、服务端连接管理、消息推送机制、心跳检测、断线重连以及与前端的实时交互实现。通过聊天系统、实时通知等案例，帮助开发者掌握使用 PHP 构建实时通信与推送服务的完整开发流程，适用于即时消息与高互动性应用场景。

2026.01.19