Python排序算法(六)——归并排序(MERGE-SORT)
有趣的事,Python永远不会缺席!
一、归并排序(MERGE-SORT)概念
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。归并排序适用于子序列有序的数据排序。
1、原理
归并排序是分治法的典型应用。分治法(Divide-and-Conquer):将原问题划分成 n 个规模较小而结构与原问题相似的子问题;递归地解决这些问题,然后再合并其结果,就得到原问题的解。从上图看分解后的数列很像一个二叉树。
归并排序采用分而治之的原理:
- 将一个序列从中间位置分成两个序列;
- 在将这两个子序列按照第一步继续二分下去;
- 直到所有子序列的长度都为1,也就是不可以再二分截止。这时候再两两合并成一个有序序列即可。
原理如上图,图片来源于https://blog.csdn.net/su_bao/article/details/81053871
2、举例
- 对以下数组进行归并排序:
[11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]
2. 首先,进行数组分组,即
[11, 99, 33 , 69, 77, 88, 55], [ 11, 33, 36,39, 66, 44, 22]
[11, 99, 33] , [69, 77, 88, 55], [ 11, 33, 36], [39, 66, 44, 22]
[11], [99, 33] , [69, 77], [88, 55],[ 11], [33, 36],[39, 66], [44, 22]
直到所有子序列的长度都为1,也就是不可以再二分截止。
[11], [99], [33] , [69], [77], [88], [55],[ 11], [33], [36],[39], [66], [44], [22]
3. 这时候再两两合并成一个有序序列即可。
[11],[33,99],[69,77],[55,88],[11],[33,36],[39,66],[22,44]
[11,33,99],[55,69,77,88],[11,33,36],[22,39,44,66]
[11,33,55,69,77,88,99],[11,22,33,36,39,44,66]
4、最终排序
[11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]
二、代码
代码用jupyternotebook实现
def merge_sort(arr):
"""归并排序"""
if len(arr) == 1:
return arr
# 使用二分法将数列分两个
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
# 使用递归运算
return marge(merge_sort(left), merge_sort(right)) def marge(left, right):
"""排序合并两个数列"""
result = []
# 两个数列都有值
while len(left) > 0 and len(right) > 0:
# 左右两个数列第一个最小放前面
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
# 只有一个数列中还有值,直接添加
result += left
result += right
return result merge_sort([11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]) # 返回结果[11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]
这里记录一下,python有一个模块,专门提供了归并排序的方法,叫做“heapq”模块,因此我们只要将分解后的结果导入该方法即可。例如:
from heapq import merge def merge_sort(lst):
if len(lst) <= 1:
return lst # 从递归中返回长度为1的序列
middle = len(lst) // 2
left = merge_sort(lst[:middle]) # 通过不断递归,将原始序列拆分成n个小序列
right = merge_sort(lst[middle:])
return list(merge(left, right)) merge_sort([11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]) # 返回结果[11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]
三、特点
比较性:排序时元素之间需要比较,所以为比较排序
稳定性:我们从代码中可以看到当左边的元素小于等于右边的元素就把左边的排前面,而原本左边的就是在前面,所以相同元素的相对顺序不变,故为稳定排序
时间复杂度: 复杂度为O(nlog^n)
空间复杂度:在合并子列时需要申请临时空间,而且空间大小随数列的大小而变化,所以空间复杂度为O(n)
记忆方法:所谓归并肯定是要先分解,再合并
结果
Successfully !!!
有趣的事,Python永远不会缺席!还不来加我,瞅什么瞅。
最新文章
- 分析器错误消息: 未能加载类型“Automation.Web.MvcApplication”。
- CALayer
- 最短的可通过编译的C语言程序
- 当一个页面出现多个checkbox全选时的处理
- html + js 右 点击 弹出 菜单
- 不关闭seLinux解决vsftpd服务本地用户不能登录问题(500 OOPS: cannot change directory:/home/***
- 关于集合set ---STL
- html5 渐变按钮练习
- Hadoop学习------Hadoop安装方式之(三):分布式部署
- (转)final修饰基本类型和引用类型变量的区别
- 微信公众号 几种移动端UI框架介绍
- [开源项目]Shell4Win,一个在Windows下执行shell命令的解释器
- react入门-组件方法、数据和生命周期
- thinkphp %s %d %f
- sql中根据逗号分隔,查出多行数据
- jQuery弹出遮罩层效果完整示例
- C#应用视频教程3.3 Halcon+C#测试
- hive 相关异常
- for each/in/of的解释and example
- scrapy框架的持久化存储