温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

如何使用Python实现的归并排序算法

发布时间:2022-01-17 09:17:57 来源:亿速云 阅读:181 作者:小新 栏目:大数据

这篇文章给大家分享的是有关如何使用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个元素,然后分别对两个子序列递归操作,直到子序列只有一个元素为止。

如何使用Python实现的归并排序算法

归并排序-分割
 

上面的步骤完成了分割,接下来开始合并了。最小的两个子序列是94和45,于是合并这两个子序列,得到序列[45, 94],另外的子序列是[33, 82],于是合并这两个子序列就得到左半部分[33, 45, 82, 94]。

如何使用Python实现的归并排序算法

归并排序-合并
 

这里元素较少,你可能并没有看清楚,就得到了左半部分有序子序列(前4个元素)。同样的操作我们得到后面5个元素的有序子序列,最后来合并这两个子序列。下文会详细说明。

[33, 45, 82, 94]
[23, 25, 59, 65, 94]
 

合并的过程都是一样的,下面gif动图清楚地演示了两个子序列的合并过程。(由于受公众号的限制,无法给出完成的演示)。完整演示可以看后面的视频。

如何使用Python实现的归并排序算法

 

参考代码

下面是用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实现的归并排序算法”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI