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

程序员文章站 2022-05-19 07:57:14

...

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

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤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 

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


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


def merge_sort(lst): #此方法来自*

 if len(lst) 

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


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


from heapq import merge

def merge_sort(seq):
 if len(seq) 声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn核实处理。
相关文章
相关视频



一文了解Python中如何使用query()进行优...


python fabric实现远程操作和部署示例


python抓取网页中的图片示例


简单谈谈Python中的闭包


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




Python 简介


Python 环境搭建


Python 中文编码


Python 基础语法


Python 变量类型




网友评论
文明上网理性发言，请遵守 新闻评论服务协议
我要评论










专题推荐


独孤九贱-php全栈开发教程全栈  170W+
主讲：Peter-Zhu  轻松幽默、简短易学，非常适合PHP学习入门


玉女心经-web前端开发教程入门  80W+
主讲：灭绝师太  由浅入深、明快简洁，非常适合前端学习入门


天龙八部-实战开发教程实战  120W+
主讲：西门大官人 思路清晰、严谨规范，适合有一定web编程基础学习