python归并排序的实现原理
2023-03-20 15:31:54 时间
原理分析
1、把一个序列从中间位置分成两个序列;
2、把这两个子序列按第一步继续分成两部分;
3、直到所有子序列的长度都是1,也就是说,不能再有二分截止。此时再两两合并成一个有序的序列。
实例
def merge(arr, low, mid, high): # low 和 high 为整个数组的第一个和最后一个位置索引,mid 为中间位置索引 # i 和 j 为指针,最初位置分别为两个有序序列的起始位置 # ltmp 用来存放合并后的序列 i = low j = mid+1 ltmp = [] while i <= mid and j <= high: # 只要左右两边都有数 if arr[i] < arr[j]: # 当左边的数小于右边的数 ltmp.append(arr[i]) # 将左边的数存入 ltmp i += 1 # 左边的指针往右移一位 else: # 当右边的数小于左边的数 ltmp.append(arr[j]) # 将右边的数存入 ltmp j += 1 # 右边的指针往右移一位 # 上面的 while 语句执行完后,左边或者右边没有数了 while i <= mid: # 当左边还有数的时候 ltmp.append(arr[i]) # 将左边剩下的数全部存入 ltmp i += 1 while j <= high: # 当右边还有数的时候 ltmp.append(arr[j]) # 将右边剩下的数全部存入 ltmp j += 1 arr[low:high+1] = ltmp # 将排序后的数组写回原数组 def merge_sort(arr, low, high): # low 和 high 为整个数组的第一个和最后一个位置索引 if low < high: # 至少有两个元素 mid = (low + high) // 2 merge_sort(arr, low, mid) # 把左边递归分解 merge_sort(arr, mid+1, high) # 把右边递归分解 merge(arr, low, mid, high) # 做归并
以上就是python归并排序的实现原理,希望对大家有所帮助。更多Python学习指路:python基础教程
本文教程操作环境:windows7系统、Python 3.9.1,DELL G3电脑。
相关文章
- 日志到底应该怎么打印?
- 前后端接口鉴权全解Cookie/Session/Token的区别
- 四种 Python 连接 MySQL 数据库的方法
- 前端基础知识整理汇总一
- Python 操作 MySQL 数据库的三个模块
- TinyDB 一个纯Python编写的轻量级数据库
- 一张五亿数据量的表执行不了,开发和DBA差点大打出手……
- 太全了!用Python操作MySQL的使用教程集锦!
- 实现动态展示多算法,这个Python库助你发现网络图社区结构
- 相同执行计划,为何有执行快慢的差别
- 如何使用Python算法进行交易
- 5G变1G,线上日志瘦身还有这些骚操作
- 巧用ActionFilterAttribute实现API日志的记录
- 聊一聊函数之美
- 提升编码水平,这本Python软件工程开源书籍为研究人员量身打造
- 使用Func<T, TResult> 委托实现API日志的记录
- React中的任务饥饿行为
- 如何在Python中操作MySQL?
- 一篇长文帮你彻底搞懂React的调度机制原理
- JDK15类的后半生:准备、解析、初始化、卸载过程详解