python编程实现归并排序的方法介绍

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python编程实现归并排序的方法介绍，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1783字，纯文字阅读大概需要3分钟。

内容图文

这篇文章主要为大家详细介绍了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编程实现归并排序的方法介绍的详细内容，更多请关注Gxl网其它相关文章！

内容总结

以上是互联网集市为您收集整理的python编程实现归并排序的方法介绍全部内容，希望文章能够帮你解决python编程实现归并排序的方法介绍所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---