这篇文章给大家分享的是有关如何使用Python实现的归并排序算法的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。
归并排序（英语：Merge sort），是创建在归并操作上的一种有效的排序算法，效率为 。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行[1]。
采用分治法:
看完上面的定义，如果你感到有点懵，那就对了本文就是写给你的。我们通过图文来详细地介绍算法的流程。算法的核心只有4个字分割和合并。
假定我们对下面的序列，按照从小到大进行排序。
94, 45, 82, 33, 25, 59, 94, 65, 23
当然你很快地手动就能完成排序任务，但30万个数字你可能就会崩溃了。还是先来看这个例子，先将这个序列平均分割。一共有9个数字，取中间位置是4.5，取整的结果为4。分成两个子序列，前4个元素和后5个元素，然后分别对两个子序列递归操作，直到子序列只有一个元素为止。
上面的步骤完成了分割，接下来开始合并了。最小的两个子序列是94和45，于是合并这两个子序列，得到序列[45, 94]，另外的子序列是[33, 82]，于是合并这两个子序列就得到左半部分[33, 45, 82, 94]。
这里元素较少，你可能并没有看清楚，就得到了左半部分有序子序列（前4个元素）。同样的操作我们得到后面5个元素的有序子序列，最后来合并这两个子序列。下文会详细说明。
计算
安全
数据库
网络和加速
企业服务
[33, 45, 82, 94][23, 25, 59, 65, 94]合并的过程都是一样的，下面gif动图清楚地演示了两个子序列的合并过程。（由于受公众号的限制，无法给出完成的演示）。完整演示可以看后面的视频。
下面是用Python实现的归并排序算法的代码，仅供参考：
import typing as tdef sort(data: t.List[int]): """ sort data """ if len(data) <= 1: return data mid = len(data) // 2 left = sort(data[:mid]) right = sort(data[mid:]) return merge(left, right) def merge(left: t.List[int], right: t.List[int]): """ merge two list """ i = 0 j = 0 ret = [] while i < len(left) and j < len(right): if left[i] < right[j]: ret.append(left[i]) i += 1 else: ret.append(right[j]) j += 1 if i == len(left): ret.extend(right[j:]) if j == len(right): ret.extend(left[i:]) return retif __name__ == '__main__': d = [45, 94, 33, 82, 25, 59, 94, 65, 23] data = sort(d) print(data)感谢各位的阅读！关于“如何使用Python实现的归并排序算法”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
原文链接：https://my.oschina.net/u/4591990/blog/4444316
