首页 / 算法 / 用python实现归并排序

用python实现归并排序

内容导读

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

内容图文

                
                    def merge(lfrom, lto, low, mid, high):
    i, j, k = low, mid, low
    while i < mid and j < high:
        if lfrom[i] < lfrom[j]:
            lto[k] = lfrom[i]
            i +=1else:
            lto[k] = lfrom[j]
            j +=1
        k +=1while i < mid:
        lto[k] = lfrom[i]
        i +=1
        k +=1while j < high:
        lto[k] = lfrom[j]
        j +=1
        k +=1def merge_pass(lfrom, lto, llen, slen):
    i =0while i+2*slen < llen:
        merge(lfrom, lto, i, i+slen, i+2*slen)
        i +=2*slen
    if i + slen < llen:
        merge(lfrom, lto, i, i+slen, llen)
    else:
        for j inrange(i, llen):
            lto[j] = lfrom[j]


def merge_sort(lst):
    slen, llen =1, len(lst)
    templist = [None]*llen
    while slen < llen:
        merge_pass(lst, templist, llen, slen)
        slen *=2
        merge_pass(templist, lst, llen, slen)
        slen *=2

归并排序的思想是：

  1. 跟快速排序从长序列排到短序列相反，归并排序是先排短的，再排长的。
  2. 对于一个序列，一开始视每一个元素为一个序列，两两合并。对于每一个“两两合并”，就是将两个排好序的序列合并的过程。
  3. 归并排序需要开辟和原序列一样大的空间。归并一遍的结果放到开辟的空间中。第二次的归并是从新空间归并到旧空间，如此反复就把序列排序了。
  4. 实现一共分为三个层级：
  • 最低层级： 将两个已排序序列合并
  • 中间层级：将整个序列，根据子序列长度，分别归并
  • 最高层级：将子序列长度从1开始翻倍增加，直到子序列长度和序列长度一样，归并完成。

原文：http://www.cnblogs.com/theodoric008/p/8033095.html

内容总结

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

内容备注

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

内容手机端

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

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

来源：【匿名】