python编程实现归并排序

yipeiwu_com5年前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中的floor()方法

 floor()方法返回不大于x的最大整数(向下取整)。 语法 以下是floor()方法的语法: import math math.floor( x ) 注意:此函...

win7安装python生成随机数代码分享

复制代码 代码如下:import random def genrand(small, big) :    return small + (big-small...

Python中用startswith()函数判断字符串开头的教程

函数:startswith() 作用:判断字符串是否以指定字符或子字符串开头 一、函数说明 语法:string.startswith(str, beg=0,end=len(string)...

浅析Python中yield关键词的作用与用法

前言 为了理解yield是什么,首先要明白生成器(generator)是什么,在讲生成器之前先说说迭代器(iterator),当创建一个列表(list)时,你可以逐个的读取每一项,这就叫...

利用Python批量生成任意尺寸的图片

利用Python批量生成任意尺寸的图片

实现效果 通过源图片,在当前工作目录的/img目录下生成1000张,分别从1*1到1000*1000像素的图片。 效果如下: 目录结构 实现示例 # -*- coding: ut...