欢迎来到Introzo百科
Introzo百科
归并排序详解(python实现)
首先归并排序使用了二分法,归根到底的思想还是分而治之。拿到一个长数组,将其不停的分为左边和右边两份,然后以此递归分下去。然后再将她们按照两个有序数组的样子合并起来。这样说起来可能很难理解,于是给出一张我画的图。
这里显示了归并排序的第一步,将数组按照middle进行递归拆分,最后分到最细之后再将其使用对两个有序数组进行排序的方法对其进行排序。
两个有序数组排序的方法则非常简单,同时对两个数组的第一个位置进行比大小,将小的放入一个空数组,然后被放入空数组的那个位置的指针往后 移一个,然后继续和另外一个数组的上一个位置进行比较,以此类推。到最后任何一个数组先出栈完,就将另外i一个数组里的所有元素追加到新数组后面。
由于递归拆分的时间复杂度是logN 然而,进行两个有序数组排序的方法复杂度是N该算法的时间复杂度是N*logN 所以是NlogN。
根据这波分析,我们可以看看对上图的一个行为。
当最左边的分到最细之后无法再划分左右然后开始进行合并。
第一次组合完成[4, 7]的合并
第二次组合完成[4, 7, 8]的合并
第三次组合完成[3, 5]的合并
第四次组合完成[3, 5, 9]的合并
第五次组合完成[3, 4, 5, 7, 8, 9]的合并结束排序。
#!/usr/bin/python
# -*- coding:utf-8 -*-
# project : 数据结构
# user :taihe
# Author: 冀恩开
# createtime :2018/8/14 15:19def merge(a, b):c = []h = j = 0while j < len(a) and h < len(b):if a[j] < b[h]:c.append(a[j])j += 1else:c.append(b[h])h += 1if j == len(a):for i in b[h:]:c.append(i)else:for i in a[j:]:c.append(i)return cdef merge_sort(lists):if len(lists) <= 1:return listsmiddle = len(lists)//2left = merge_sort(lists[:middle])right = merge_sort(lists[middle:])return merge(left, right)if __name__ == '__main__':a = [4, 7, 8, 3, 5, 9]print( merge_sort(a))
原文https://www.introzo.com/piperck/p/6030122.html
相关文章
- 10-05 戈多的场景树
- 10-05 戈多动画
- 10-05 在 Godot 中设计标题画面
- 10-05 信息搜索和可视化
- 10-05 设计流程与任务分析
- 10-05 颤动警报对话框
- 10-05 PostgreSQL远程连接配置管理/账号密码分配
- 10-05 Windows server 创建FTP 包括ft
- 10-05 Mongodb副本集加分片集群安全认证使用账号密码
- 10-05 浅谈ubuntu中执行.sh文件的几种方式的区别
- 10-05 Linux性能优化的实用思路和技巧(linux性能
- 10-05 如何轻松安装Linux系统显卡驱动(Linux安装
- 10-05 win10动态锁设置教程
- 10-05 win10关闭Win10右下角提示的教程
- 10-05 win10设置定时提醒闹钟方法
- 10-05 win10音频服务未运行 错误1068怎么办
- 10-05 win10哪里下载
- 10-05 Win10命令提示符打不开怎么办
- 10-05 实现发送模板消息功能的微信小程序示例【通过open
- 10-05 微信公众平台发送模板消息(Java接口开发)
- 最近发表