个人中心
gpt4 book ai didi

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

转载 作者：qq735679552 更新时间：2022-09-29 22:32:09 24 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章Python编程中归并排序算法的实现步骤详解由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

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

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

例如一个无序数组 。

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

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

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

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

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

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

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

初始:

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

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

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

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

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

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

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

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

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

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

最终得到排序结果 。

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

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

方法1：将前面讲述的过程翻译过来了，略先拙笨 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#! /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()方法，代码更紧凑简洁 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#! /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中就提供了归并排序的方法，只要将分解后的结果导入该方法即可.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#! /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)

最后此篇关于Python编程中归并排序算法的实现步骤详解的文章就讲到这里了,如果你想了解更多关于Python编程中归并排序算法的实现步骤详解的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

24 4 0
文章推荐： 使用Python判断质数(素数)的简单方法讲解
文章推荐： php从身份证获取性别和出生年月
文章推荐： Yii2框架实现数据库常用操作总结
文章推荐： Yii2实现中国省市区三级联动实例
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com