你需要知道的九大排序算法【Python实现】之归并排序
2024-10-02 01:40:58
四、归并排序
基本思想:归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。归并过程:比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1;否则将第二个有序表中的元素a[j]复制到r[k]中,并令j和k分别加上1,如此循环下去,直到其中一个有序表取完,然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现,先把待排序区间[s,t]以中点二分,接着把左边子区间排序,再把右边子区间排序,最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
算法实现:
#coding: utf-8 #!/usr/bin/python import random #随机生成0~100之间的数值 def get_andomNumber(num): lists=[] i=0 while i<num: lists.append(random.randint(0,100)) i+=1 return lists # 归并排序 def merge(left, right): i, j = 0, 0 result = [] while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result += left[i:] result += right[j:] return result def merge_sort(lists): if len(lists) <= 1: return lists num = len(lists) // 2 # python3 整数除法/会变浮点,改为// left = merge_sort(lists[:num]) right = merge_sort(lists[num:]) return merge(left, right) a = get_andomNumber(10) print("排序之前:%s" %a) b = merge_sort(a) print("排序之后:%s" %b)
最新文章
- BW基于ALE的主数据增量机制分析
- Video Codecs by FOURCC 视频格式编码
- matlab中max的用法
- DataSource绑定DataTable.Select()显示system.data.DataRow问题解决的方法
- Restful随笔
- oracle 通过同义词建立视图
- 全局变量&;局部变量,global&;nonlocal
- STL - 各个容器的使用时机
- syncer.go
- PowerPoint 中插入 Latex 公式
- windows环境下python编码问题
- Spring Boot微服务如何集成fescar解决分布式事务问题?
- vue-router跳转
- Git+Gitlab+Ansible剧本实现一键部署动态网站(二)--技术流ken
- windows 上用 docker 部署aspnetcore 2.0
- 该问题是需要导包!!!需要pom中添加依赖The absolute uri: http://java.sun.com/jsp/jstl/core cannot be resolved in either web.xml or the jar files deployed with this application
- 最简单的TTcpServer与TTcpClient通信实例-Delphi
- css定位研究
- 第一次java实验报告
- Swift 开发中,为什么要远离 Heap?