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

yipeiwu_com5年前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)

相关文章

djang常用查询SQL语句的使用代码

djang常用查询SQL语句的使用代码

将django语法和sql对应一下,希望对大家有所帮助 查询单个列的值 story.object.values_list("url", flat=True) SELECT `sto...

一文总结学习Python的14张思维导图

一文总结学习Python的14张思维导图

本文主要涵盖了 Python 编程的核心知识(暂不包括标准库及第三方库,后续会发布相应专题的文章)。 首先,按顺序依次展示了以下内容的一系列思维导图:基础知识,数据类型(数字,字符串,列...

python之DataFrame实现excel合并单元格

python之DataFrame实现excel合并单元格

在工作中经常遇到需要将数据输出到excel,且需要对其中一些单元格进行合并,比如如下表表格,需要根据A列的值,合并B、C列的对应单元格 pandas中的to_excel方法只能对索引进...

python 根据字典的键值进行排序的方法

python 根据字典的键值进行排序的方法

1、利用key排序 d = {'d1':2, 'd2':4, 'd4':1,'d3':3,} for k in sorted(d): print(k,d[k]) d1 2 d2...

浅谈python已知元素,获取元素索引(numpy,pandas)

目前搜索到的方法有: np.where(‘元素') 还有就是pandas的方法: df.index(‘元素') 但是第二个方法的问题就是会报错,嗯,这就比较尴尬了,查询了网上的解决方案,...