python编程实现归并排序

因为上个星期leetcode的一道题(Median of Two Sorted Arrays)所以想仔细了解一下归并排序的实现。

还是先阐述一下排序思路：

首先归并排序使用了二分法，归根到底的思想还是分而治之。拿到一个长数组，将其不停的分为左边和右边两份，然后以此递归分下去。然后再将她们按照两个有序数组的样子合并起来。这样说起来可能很难理解，于是给出一张我画的图。

这里显示了归并排序的第一步，将数组按照middle进行递归拆分，最后分到最细之后再将其使用对两个有序数组进行排序的方法对其进行排序。

两个有序数组排序的方法则非常简单，同时对两个数组的第一个位置进行比大小，将小的放入一个空数组，然后被放入空数组的那个位置的指针往后移一个，然后继续和另外一个数组的上一个位置进行比较，以此类推。到最后任何一个数组先出栈完，就将另外i一个数组里的所有元素追加到新数组后面。

由于递归拆分的时间复杂度是logN 然而，进行两个有序数组排序的方法复杂度是N该算法的时间复杂度是N*logN 所以是NlogN。

根据这波分析，我们可以看看对上图的一个行为。

当最左边的分到最细之后无法再划分左右然后开始进行合并。

第一次组合完成[4, 7]的合并

第二次组合完成[4, 7, 8]的合并

第三次组合完成[3, 5]的合并

第四次组合完成[3, 5, 9]的合并

第五次组合完成[3, 4, 5, 7, 8, 9]的合并结束排序。

下面放上python的代码

def merge(a, b):
 c = []
 h = j = 0
 while j < len(a) and h < len(b):
  if a[j] < b[h]:
   c.append(a[j])
   j += 1
  else:
   c.append(b[h])
   h += 1

 if j == len(a):
  for i in b[h:]:
   c.append(i)
 else:
  for i in a[j:]:
   c.append(i)

 return c


def merge_sort(lists):
 if len(lists) <= 1:
  return lists
 middle = len(lists)/2
 left = merge_sort(lists[:middle])
 right = merge_sort(lists[middle:])
 return merge(left, right)


if __name__ == '__main__':
 a = [4, 7, 8, 3, 5, 9]
 print merge_sort(a)

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。

# python # 归并排序 # python 实现归并排序算法 # Python编程中归并排序算法的实现步骤详解 # python实现归并排序算法 # Python实现的归并排序算法示例 # python实现折半查找和归并排序算法 # Python排序搜索基本算法之归并排序实例分析 # 10个python3常用排序算法详细说明与实例（快速排序 # 冒泡排序 # 桶排序 # 基数排序 # 堆排序 # 希尔排序 # 计数排序） # golang/python实现归并排序实例代码 # python基本算法之实现归并排序(Merge sort) # 递归 # 再将 # 分而治之 # 很难 # 将其 # 以此类推 # 我们可以 # 对其 # 任何一个 # 另外一个 # 就将 # 上个 # 第四次 # 放上 # 两份 # 到新 # 大家多多 # 第五次 # 上图 # 组里

返回目录在线咨询

上一篇：如何在PHP模板建站系统中集成第三方支付接口？
下一篇：如何理解Golang作用域规则_Golang变量作用域说明

您的项目需求

*请认真填写需求信息，我们会在24小时内与您取得联系。

全网整合营销服务商

python编程实现归并排序

您的项目需求