首页 / 算法 / 数据结构与算法 -- Python实现【归并排序算法】

数据结构与算法 -- Python实现【归并排序算法】

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法 -- Python实现【归并排序算法】，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含899字，纯文字阅读大概需要2分钟。

内容图文

摘要：

本文主要介绍的是python实现归并排序算法，本文首先会介绍归并排序的原理，并以一张思维导图来加深读者对该算法过程的理解，紧接着进行代码的实现。最后介绍该算法的时间复杂度。

一.原理：

1.将一个序列从中间位置分成两个序列；

2.在将这两个子序列按照第一步继续二分下去；

3.直到所有子序列的长度都为1，也就是不可以再二分截止。这时候再两两合并成一个有序序列即可。

 

下面的这张图片可以很清晰的解释该原理：

技术分享图片

 

 

二.代码如下： 

            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 = [14, 2, 34, 43, 21, 19]
    print (merge_sort(a))

 

 时间复杂度：

  • 最优时间复杂度：O(nlongn)

    最坏时间复杂度 ：O(nlongn)

    稳定性：稳定

     

参考链接：https://blog.csdn.net/su_bao/article/details/81053871

原文：https://www.cnblogs.com/gengyufei/p/13279950.html

内容总结

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

内容备注

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

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1193543.html

来源：【匿名】