python编程实现归并排序

yipeiwu_com6年前Python基础

因为上个星期leetcode的一道题(Median of Two Sorted Arrays)所以想仔细了解一下归并排序的实现。

还是先阐述一下排序思路:

首先归并排序使用了二分法,归根到底的思想还是分而治之。拿到一个长数组,将其不停的分为左边和右边两份,然后以此递归分下去。然后再将她们按照两个有序数组的样子合并起来。这样说起来可能很难理解,于是给出一张我画的图。

这里显示了归并排序的第一步,将数组按照middle进行递归拆分,最后分到最细之后再将其使用对两个有序数组进行排序的方法对其进行排序。

两个有序数组排序的方法则非常简单,同时对两个数组的第一个位置进行比大小,将小的放入一个空数组,然后被放入空数组的那个位置的指针往后 移一个,然后继续和另外一个数组的上一个位置进行比较,以此类推。到最后任何一个数组先出栈完,就将另外i一个数组里的所有元素追加到新数组后面。

由于递归拆分的时间复杂度是logN 然而,进行两个有序数组排序的方法复杂度是N该算法的时间复杂度是N*logN 所以是NlogN。

根据这波分析,我们可以看看对上图的一个行为。

当最左边的分到最细之后无法再划分左右然后开始进行合并。

第一次组合完成[4, 7]的合并

第二次组合完成[4, 7, 8]的合并

第三次组合完成[3, 5]的合并

第四次组合完成[3, 5, 9]的合并

第五次组合完成[3, 4, 5, 7, 8, 9]的合并结束排序。

下面放上python的代码

def merge(a, b):
 c = []
 h = j = 0
 while j < len(a) and h < len(b):
  if a[j] < b[h]:
   c.append(a[j])
   j += 1
  else:
   c.append(b[h])
   h += 1

 if j == len(a):
  for i in b[h:]:
   c.append(i)
 else:
  for i in a[j:]:
   c.append(i)

 return c


def merge_sort(lists):
 if len(lists) <= 1:
  return lists
 middle = len(lists)/2
 left = merge_sort(lists[:middle])
 right = merge_sort(lists[middle:])
 return merge(left, right)


if __name__ == '__main__':
 a = [4, 7, 8, 3, 5, 9]
 print merge_sort(a)

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

相关文章

Python入门教程4. 元组基本操作 原创

前面简单介绍了Python列表基本操作,这里再来简单讲述一下Python元组相关操作 >>> dir(tuple) #查看元组的属性和方法 ['__add__',...

python3.7环境下安装Anaconda的教程图解

python3.7环境下安装Anaconda的教程图解

下载Anaconda安装包 官网下载或是在清华大学镜像站下载,我安装的是下面这个版本:   安装过程 配置环境 将anaconda的scripts文件夹路径添...

在Python中使用filter去除列表中值为假及空字符串的例子

在 Python中,认为以下值为假: None # None值 False # False值 0 # 数值零不管它是int,float还是complex类型 '',(),[] #...

django开发之settings.py中变量的全局引用详解

django开发之settings.py中变量的全局引用详解

本文主要介绍的是django中settings.py中变量的全局引用的相关资料,下面话不多说,来看看详细的介绍吧。 前言 在settings.py中添加自定义变量,可以通过setting...

使用 python pyautogui实现鼠标键盘控制功能

pyautogui是一个可以控制鼠标和键盘的python库,类似的还有pywin32。 pyautogui的安装 pip3 install python3-xlib 依赖库 sudo a...