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)

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

时间: 2017-04-13

python里对list中的整数求平均并排序

问题 定义一个int型的一维数组,包含40个元素,用来存储每个学员的成绩,循环产生40个0~100之间的随机整数, (1)将它们存储到一维数组中,然后统计成绩低于平均分的学员的人数,并输出出来. (2)将这40个成绩按照从高到低的顺序输出出来. 解决(python) #! /usr/bin python #coding:utf-8 from __future__ import division #实现精确的除法,例如4/3=1.333333 import random def make_scor

Python编程中归并排序算法的实现步骤详解

基本思想:归并排序是一种典型的分治思想,把一个无序列表一分为二,对每个子序列再一分为二,继续下去,直到无法再进行划分为止.然后,就开始合并的过程,对每个子序列和另外一个子序列的元素进行比较,依次把小元素放入结果序列中进行合并,最终完成归并排序. 归并操作过程: 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 设定两个指针,最初位置分别为两个已经排序序列的起始位置 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置 重复步骤3直到某一指针达到序列尾

python常见排序算法基础教程

前言:前两天腾讯笔试受到1万点暴击,感觉浪费我两天时间去牛客网做题--这篇博客介绍几种简单/常见的排序算法,算是整理下. 时间复杂度 (1)时间频度一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道.但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了.并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多.一个算法中的语句执行次数称为语句频度或时间频度.记为T(n). (2)时间复

python sort、sorted高级排序技巧

Python list内置sort()方法用来排序,也可以用python内置的全局sorted()方法来对可迭代的序列排序生成新的序列. 1)排序基础 简单的升序排序是非常容易的.只需要调用sorted()方法.它返回一个新的list,新的list的元素基于小于运算符(__lt__)来排序. 复制代码 代码如下: >>> sorted([5, 2, 3, 1, 4]) [1, 2, 3, 4, 5] 你也可以使用list.sort()方法来排序,此时list本身将被修改.通常此方法不如s

Python中字典(dict)和列表(list)的排序方法实例

一.对列表(list)进行排序 推荐的排序方式是使用内建的sort()方法,速度最快而且属于稳定排序 复制代码 代码如下: >>> a = [1,9,3,7,2,0,5]>>> a.sort()>>> print a[0, 1, 2, 3, 5, 7, 9]>>> a.sort(reverse=True)>>> print a[9, 7, 5, 3, 2, 1, 0]>>> b = ['e','a'

python编程实现希尔排序

观察一下"插入排序":其实不难发现她有个缺点: 如果当数据是"5, 4, 3, 2, 1"的时候,此时我们将"无序块"中的记录插入到"有序块"时,估计俺们要崩盘,每次插入都要移动位置,此时插入排序的效率可想而知. shell根据这个弱点进行了算法改进,融入了一种叫做"缩小增量排序法"的思想,其实也蛮简单的,不过有点注意的就是: 增量不是乱取,而是有规律可循的. 希尔排序时效分析很难,关键码的比较次数与记录移

python 实现归并排序算法

理论不多说: 复制代码 代码如下: #!/usr/bin/python import sys def merge(array, q, p, r): left_array = array[q:p+1] right_array = array[p+1:r+1] left_array_num = len(left_array) right_array_num = len(right_array) i, j , k= [0, 0, q] while i < left_array_num and j <

python字符串排序方法

本文以实例形式简述了Python实现字符串排序的方法,是Python程序设计中一个非常实用的技巧.分享给大家供大家参考之用.具体方法如下: 一般情况下,python中对一个字符串排序相当麻烦: 一.python中的字符串类型是不允许直接改变元素的.必须先把要排序的字符串放在容器里,如list. 二.python中的list容器的sort()函数没返回值. 所以在python中对字符串排序往往需要好几行代码. 具体实现方法如下: >>> s = "string" >

python 快速排序代码

复制代码 代码如下: def quick_sort(ls): return [] if ls == [] else quick_sort([y for y in ls[1:] if y < ls[0]]) + [ls[0]] + quick_sort([y for y in ls[1:] if y >= ls[0]]) if __name__ == '__main__': l1 = [3,56,8,1,34,56,89,234,56,231,45,90,33,66,88,11,22] l2 =

Python中对列表排序实例

很多时候,我们需要对List进行排序,Python提供了两个方法,对给定的List L进行排序: 方法1.用List的成员函数sort进行排序 方法2.用built-in函数sorted进行排序(从2.4开始) 这两种方法使用起来差不多,以第一种为例进行讲解: 从Python2.4开始,sort方法有了三个可选的参数,Python Library Reference里是这样描述的 复制代码 代码如下: cmp:cmp specifies a custom comparison function

Python中元组,列表,字典的区别

Python中,有3种内建的数据结构:列表.元组和字典. 1.列表 list是处理一组有序项目的数据结构,即你可以在一个列表中存储一个序列的项目.列表中的项目.列表中的项目应该包括在方括号中,这样python就知道你是在指明一个列表.一旦你创建了一个列表,你就可以添加,删除,或者是搜索列表中的项目.由于你可以增加或删除项目,我们说列表是可变的数据类型,即这种类型是可以被改变的,并且列表是可以嵌套的. 实例: #coding=utf-8 animalslist=['fox','tiger','ra

Python 中迭代器与生成器实例详解

Python 中迭代器与生成器实例详解 本文通过针对不同应用场景及其解决方案的方式,总结了Python中迭代器与生成器的一些相关知识,具体如下: 1.手动遍历迭代器 应用场景:想遍历一个可迭代对象中的所有元素,但是不想用for循环 解决方案:使用next()函数,并捕获StopIteration异常 def manual_iter(): with open('/etc/passwd') as f: try: while True: line=next(f) if line is None: br

Python中数组,列表:冒号的灵活用法介绍(np数组,列表倒序)

让我们来看一个例子: import numpy as np x=np.array([[1,2,3],[5,6,7],[7,8,9]]) print(x) Out[64]: array([[1, 2, 3], [5, 6, 7], [7, 8, 9]]) 以上的结果我想大家应该没问题把,就是定义了一个np数组,关键在下面 print(x[:,::-1]) Out[65]: [[3 2 1] [7 6 5] [9 8 7]] 以上的代码实现了一种功能,就是将数组倒序排列了,每个维度上倒序,这段代码怎

Python实现的列表排序、反转操作示例

本文实例讲述了Python实现的列表排序.反转操作.分享给大家供大家参考,具体如下: 排序: 使用sorted方法和列表的sort方法: sorted方法适用范围更广,sort方法只有列表有. li = [{'a':'23'}, {'a':'12'}] def sort_fun(mp): s = mp['a'] return int(s) print(sorted(li, key = sort_fun, reverse = True)) #这会返回一个排好序的列表,原列表不变. print(li

python中的decimal类型转换实例详解

[Python标准库]decimal--定点数和浮点数的数学运算 作用:使用定点数和浮点数的小数运算.         Python 版本:2.4 及以后版本 decimal 模块实现了定点和浮点算术运算符,使用的是大多数人所熟悉的模型,而不是程序员熟悉的模型,即大多数计算机硬件实现的 IEEE 浮点数运算.Decimal 实例可以准确地表示任何数,对其上取整或下取整,还可以对有效数字个数加以限制. Decimal 小数值表示为 Decimal 类的实例.构造函数取一个整数或字符串作为参数.使用

python函数调用,循环,列表复制实例

我就废话不多说了,大家还是直接看代码吧! year=int(raw_input('year:\n')) month=int(raw_input('month:\n')) day=int(raw_input('day:\n')) sum=0 months=(0,31,59,90,120,151,181,212,243,273,304,334) if 0<month<=12: sum=months[month-1] else: print 'data error!' sum+=day leap=0

Python中动态创建类实例的方法

简介 在Java中我们可以通过反射来根据类名创建类实例,那么在Python我们怎么实现类似功能呢? 其实在Python有一个builtin函数import,我们可以使用这个函数来在运行时动态加载一些模块.如下: def createInstance(module_name, class_name, *args, **kwargs): module_meta = __import__(module_name, globals(), locals(), [class_name]) class_met

对arraylist中元素进行排序实例代码

rrayList中的元素进行排序,主要考查的是对util包中的Comparator接口和Collections类的使用. 实现Comparator接口必须实现compare方法,自己可以去看API帮助文档. 创建一个Comparator实例后,用Collections.sort(List,<E>)对List中的元素进行排序. 下面是实现代码: 以下文件必须引入util包: package com.test; import Java.util.*; Emp.java文件如下: class Emp

Python中实现switch功能实例解析

前言 今天在学习python的过程中,发现python没有switch这个语法.于是就想在python中如何才能实现这个功能呢? 正文 本文中我们对switch的使用模拟为正常的数据库的增删改查操作的对应,如'select 对应'select action'等. 1.简单的if-else 正如我们所知,python中有if语句,而且当时学习C的时候,学到if-else时引出的的替代品就是switch,两者可以完美的互相替代,需要注意的是在python中else if简化成了elif.如下所示: