python实现归并排序算法

yipeiwu_com7年前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采用Django开发自己的博客系统

Python采用Django开发自己的博客系统

好久之前就想做一下自己的博客系统了,但是在网上查了查好像是需要会一些Node.js的相关知识,而且还要安装辣么多的库什么的,就不想碰了。但是我遇到了Django这么一款神器,没想到我的博...

使用IPython来操作Docker容器的入门指引

现在Docker是地球上最炙手可热的项目之一,就意味着人民实际上不仅仅是因为这个才喜欢它。 话虽如此,我非常喜欢使用容器,服务发现以及所有被创造出的新趣的点子和领域来切换工作作为范例。...

Python中遇到的小问题及解决方法汇总

Python中遇到的小问题及解决方法汇总

本文会把学习过程中遇到的一些小问题和解决办法放在这里,以便于大家能够更好地学习python。 一、Python的异常处理 因为想到自己不断尝试写小程序的话会用到抛出异常信息来判断哪里出现...

python函数局部变量、全局变量、递归知识点总结

函数局部变量 全局变量 及其作用域 #简单类型(int str等)变量的局部变量与全局变量及其作用域的关系 name = "xxx" #第一级顶头定义的变量都称为全局变量,其作用域从...

Python3.7中安装openCV库的方法

1.首先自己直接在cmd中输入 pip3 install openCV是不可行的,即需要自己下载安装包本地安装 2.openCV库 下载地址http://www.lfd.uci.edu/...