python 归并排序

发布时间:2022-05-09 09:53:23 人气:79 作者:多测师

  原理

  归并操作(归并算法),指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。

  步骤

  1.迭代法

  申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列

  设定两个指针,最初位置分别为两个已经排序序列的起始位置

  3.比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置

  重复步骤3直到某一指针到达序列尾

  将另一序列剩下的所有元素直接复制到合并序列尾

  递归法

  假设序列共有n个元素:

  将序列每相邻两个数字进行归并操作,形成 {\displaystyle floor(n/2)} floor(n/2)个序列,排序后每个序列包含两个元素

  将上述序列再次归并,形成 {\displaystyle floor(n/4)} floor(n/4)个序列,每个序列包含四个元素

  重复步骤2,直到所有元素排序完毕

python 归并排序

  代码

  # 递归法

  def merge_sort(list):

  # 认为长度不大于1的数列是有序的

  if len(list) <= 1:

  return list

  # 二分列表

  middle = len(list) // 2

  left = merge_sort(list[:middle])

  right = merge_sort(list[middle:])

  # 最后一次合并

  return merge(left, right)

  # 合并

  def merge(left, right):

  l,r=0,0

  result=[]

  while l

  if left[l]

  result.append(left[l])

  l+=1

  else:

  result.append(right[r])

  r +=1

  reslut +=left[l:]

  result+=right[r:]

  return result

  以上内容为大家介绍了python 归并排序,希望对大家有所帮助,如果想要了解更多Python相关知识,请关注多测师。https://www.e70w.com/xwzx/


上一篇:python 希尔排序
下一篇:python 快速排序
返回列表
在线客服
联系方式

热线电话

17727591462

上班时间

周一到周五

二维码
线