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

基本思想:归并排序是一种典型的分治思想,把一个无序列表一分为二,对每个子序列再一分为二,继续下去,直到无法再进行划分为止。然后,就开始合并的过程,对每个子序列和另外一个子序列的元素进行比较,依次把小元素放入结果序列中进行合并,最终完成归并排序。
归并操作过程:

申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
设定两个指针,最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
重复步骤3直到某一指针达到序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
上述说法是理论表述,下面用一个实际例子说明:

例如一个无序数组

[6,2,3,1,7]

首先将这个数组通过递归方式进行分解,直到:

[6],[2],[3],[1],[7]

然后开始合并排序,也是用递归的方式进行:

两个两个合并排序,得到:

[2,6],[1,3],[7]

上一步中,其实也是按照本步骤的方式合并的,只不过由于每个list中一个数,不能完全显示过程。下面则可以完全显示过程。

初始:

 a = [2,6] b = [1,3] c = [] 

第1步,顺序从a,b中取出一个数字:2,1 比较大小后放入c中,并将该数字从原list中删除,结果是:

a = [2,6] b = [3] c = [1] 

第2步,继续从a,b中按照顺序取出数字,也就是重复上面步骤,这次是:2,3 比较大小后放入c中,并将该数字从原list中删除,结果是:

a = [6] b = [3] c = [1,2] 

第3步,再重复前边的步骤,结果是:

a = [6] b = [] c = [1,2,3] 

最后一步,将6追加到c中,结果形成了:

a = [] b = [] c = [1,2,3,6]

通过反复应用上面的流程,实现[1,2,3,6]与[7]的合并

最终得到排序结果

[1,2,3,6,7]

本文列举了三种python的实现方法:

方法1:将前面讲述的过程翻译过来了,略先拙笨

#! /usr/bin/env python
#coding:utf-8

def merge_sort(seq):
 if len(seq) ==1:
 return seq
 else:
 middle = len(seq)/2
 left = merge_sort(seq[:middle])
 right = merge_sort(seq[middle:])

 i = 0 #left 计数
 j = 0 #right 计数
 k = 0 #总计数

 while i < len(left) and j < len(right):
  if left[i] < right [j]:
  seq[k] = left[i]
  i +=1
  k +=1
  else:
  seq[k] = right[j]
  j +=1
  k +=1

 remain = left if i<j else right
 r = i if remain ==left else j

 while r<len(remain):
  seq[k] = remain[r]
  r +=1
  k +=1

 return seq

方法2:在按照顺序取数值方面,应用了list.pop()方法,代码更紧凑简洁

#! /usr/bin/env python
#coding:utf-8

def merge_sort(lst): #此方法来自维基百科

 if len(lst) <= 1:
 return lst

 def merge(left, right):
 merged = []

 while left and right:
  merged.append(left.pop(0) if left[0] <= right[0] else right.pop(0))

 while left:
  merged.append(left.pop(0))

 while right:
  merged.append(right.pop(0))

 return merged

 middle = int(len(lst) / 2)
 left = merge_sort(lst[:middle])
 right = merge_sort(lst[middle:])
 return merge(left, right)

方法3:原来在python的模块heapq中就提供了归并排序的方法,只要将分解后的结果导入该方法即可。

#! /usr/bin/env python
#coding:utf-8

from heapq import merge

def merge_sort(seq):
 if len(seq) <= 1:
 return m
 else:
 middle = len(seq)/2
 left = merge_sort(seq[:middle])
 right = merge_sort(seq[middle:])
 return list(merge(left, right))  #heapq.merge()

if __name__=="__main__":
 seq = [1,3,6,2,4]
 print merge_sort(seq)
时间: 2016-05-03

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里对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 快速排序代码

复制代码 代码如下: 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中字典(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中对列表排序实例

很多时候,我们需要对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编程实现希尔排序

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

python编程实现归并排序

因为上个星期leetcode的一道题(Median of Two Sorted Arrays)所以想仔细了解一下归并排序的实现. 还是先阐述一下排序思路: 首先归并排序使用了二分法,归根到底的思想还是分而治之.拿到一个长数组,将其不停的分为左边和右边两份,然后以此递归分下去.然后再将她们按照两个有序数组的样子合并起来.这样说起来可能很难理解,于是给出一张我画的图. 这里显示了归并排序的第一步,将数组按照middle进行递归拆分,最后分到最细之后再将其使用对两个有序数组进行排序的方法对其进行排序.

python常见排序算法基础教程

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

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字符串连接方法分析

本文实例分析了python字符串连接方法.分享给大家供大家参考,具体如下: python字符串连接有几种方法,把大家可能用到的列出来,第一个方法效率是最低的,另外给大家介绍后面的 2种效率高的方法,希望对大家有帮助. 先介绍下效率比较低的,有些新手朋友就会犯这个错误: a = ['a','b','c','d'] content = '' for i in a: content = content + i print content 说下为什么效率会低呢? 原因:在循环连接字符串的时候,他每次连接

python字符串的方法与操作大全

一:字符串的方法与操作 *注意:首字母为l的为从左边操作,为r的方法为从右边操作 1.__contains__()判断是否包含 判断指定字符或字符串是否包含在一个字符串内,返回值为true或者false str1="asdfgh" print(str1.__contains__('a')) print(str1.__contains__("df")) print(str1.__contains__('r')) 运行结果: True True False 作用和in相

使用Template格式化Python字符串的方法

对Python字符串,除了比较老旧的%,以及用来替换掉%的format,及在python 3.6中加入的f这三种格式化方法以外,还有可以使用Template对象来进行格式化. from string import Template,可以导入Template类. 实例化Template类需要传入一个Template模板字符串. class Template(metaclass=_TemplateMetaclass): """A string class for supporti

C语言字符串转换为Python字符串的方法

问题 怎样将C中的字符串转换为Python字节或一个字符串对象? 解决方案 C字符串使用一对 char * 和 int 来表示, 你需要决定字符串到底是用一个原始字节字符串还是一个Unicode字符串来表示. 字节对象可以像下面这样使用 Py_BuildValue() 来构建: char *s; /* Pointer to C string data */ int len; /* Length of data */ /* Make a bytes object */ PyObject *obj

Python 列表排序方法reverse、sort、sorted详解

python语言中的列表排序方法有三个:reverse反转/倒序排序.sort正序排序.sorted可以获取排序后的列表.在更高级列表排序中,后两中方法还可以加入条件参数进行排序. reverse()方法 将列表中元素反转排序,比如下面这样 >>> x = [1,5,2,3,4] >>> x.reverse() >>> x [4, 3, 2, 5, 1] reverse列表反转排序:是把原列表中的元素顺序从左至右的重新存放,而不会对列表中的参数进行排序

Python sorted排序方法如何实现

在给列表排序时,sorted非常好用,语法如下: sorted(iterable[, cmp[,key[,reverse]]]) sorted定义如下: sorted( iterable[, cmp[, key[, reverse]]]) iterable:是可迭代类型类型; cmp:用于比较的函数,比较什么由key决定,有默认值,迭代集合中的一项; key:用列表元素的某个属性和函数进行作为关键字,有默认值,迭代集合中的一项; reverse:排序规则. reverse = True 或者 r

python 随机数使用方法,推导以及字符串,双色球小程序实例

如下所示: #随机数的使用 import random #导入random random.randint(0,9)#制定随机数0到9 i=random.sample(range(1,34),6)#输出6个随机数,范围是1到34 i.sort()#排序方法,排序时更改原数组,无返回值 sorted(i)#排序函数,排序时不影响原数组,产生新的排序后数据 print('----------------用上述的随机数做一个双色球---------------------') sj=random.sam

python文件排序的方法总结

在python环境中提供两种排序方案:用库函数sorted()对字符串排序,它的对象是字符:用函数sort()对数字排序,它的对象是数字,如果读取文件的话,需要进行处理(把文件后缀名'屏蔽'). (1)首先:我测试的文件夹是/img/,里面的文件都是图片,如下图所示: (2)测试库函数sorted(),直接贴出代码: import numpy as np import os   img_path='./img/'   img_list=sorted(os.listdir(img_path))#文

Python使用中文正则表达式匹配指定中文字符串的方法示例

本文实例讲述了Python使用中文正则表达式匹配指定中文字符串的方法.分享给大家供大家参考,具体如下: 业务场景: 从中文字句中匹配出指定的中文子字符串 .这样的情况我在工作中遇到非常多, 特梳理总结如下. 难点: 处理GBK和utf8之类的字符编码, 同时正则匹配Pattern中包含汉字,要汉字正常发挥作用,必须非常谨慎.推荐最好统一为utf8编码,如果不是这种最优情况,也有酌情处理. 往往一个具有普适性的正则表达式会简化程序和代码的处理,使过程简洁和事半功倍,这往往是高手和菜鸟最显著的差别.