这篇文章给大家分享的是有关如何使用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 t
def 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 ret
if __name__ == '__main__':
d = [45, 94, 33, 82, 25, 59, 94, 65, 23]
data = sort(d)
print(data)
感谢各位的阅读!关于“如何使用Python实现的归并排序算法”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。