python实现归并排序算法

yipeiwu_com5年前Python基础

归并排序是典型的分治法的应用

思想:先递归分解数组,再合并数组

原理:将数组分解最小之后,然后合并两个有序数组,基本思想是比较两个数组的最前面的数,谁小就取谁,取完后,将相应的指针后移以为。然后再比较,直到一个数组为空,最后把另一个数组的剩余部分复制过来即可。

Python代码实现:

#归并排序
 
def merge_sort(alist):
 if len(alist) <= 1:
  return alist
 # 二分分解
 num = len(alist) / 2
 left = merge_sort(alist[:num])
 right = merge_sort(alist[num:])
 # 合并
 return merge(left, right)
 
 
def merge(left, right):
 '''合并操作,将两个有序数组left[]和right[]合并成一个大的有序数组'''
 # left与right的下标指针
 l, r = 0, 0
 result = []
 while l < len(left) and r < len(right):
  if left[l] < right[r]:
   result.append(left[l])
   l += 1
  else:
   result.append(right[r])
   r += 1
 result += left[l:]
 result += right[r:]
 return result
 
 
alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
sorted_alist = merge_sort(alist)
print(sorted_alist)

时间复杂度:

最优时间复杂度:O(nlongn)

最坏时间复杂度 :O(nlongn)

稳定性:稳定

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

Python实现通过继承覆盖方法示例

本文实例讲述了Python实现通过继承覆盖方法。分享给大家供大家参考,具体如下: Python真是太动态了,所有的方法默认都是虚的。子类定义父类同名函数之后,父类函数被覆盖。 cla...

python将人民币转换大写的脚本代码

复制代码 代码如下:def Num2MoneyFormat( change_number ):    """    .转换数字...

使用Python标准库中的wave模块绘制乐谱的简单教程

使用Python标准库中的wave模块绘制乐谱的简单教程

在本文中,我们将探讨一种简洁的方式,以此来可视化你的MP3音乐收藏。此方法最终的结果将是一个映射你所有歌曲的正六边形网格地图,其中相似的音轨将处于相邻的位置。不同区域的颜色对应不同的音乐...

python3.6中@property装饰器的使用方法示例

本文实例讲述了python3.6中@property装饰器的使用方法。分享给大家供大家参考,具体如下: 1、@property装饰器的使用场景简单记录如下: 负责把一个方法变成属性...

天翼开放平台免费短信验证码接口使用实例

对于目前众多的验证码解决方案来说,这个API有着中国电信这个重量级的运营商为靠山,应该是比较靠谱的了,而且还是免费的。详细情况请参阅:http://open.189.cn 使用方式:#定...