开发者社区> python之战> 正文

python实现归并算法

简介: 归并排序是采用分治法的一个非常典型的应用,另一个可以采用分治法的是快速排序,归并算法比快速排序速度稍低。归并排序的思想就是先递归分解数组,再合并数组。 将数组分解最小之后,然后合并两个有序数组,基本思路是比较两个数组的最前面的数,谁小就先取谁,取了后相应的指针就往后移一位。
+关注继续查看

归并排序是采用分治法的一个非常典型的应用,另一个可以采用分治法的是快速排序,归并算法比快速排序速度稍低。归并排序的思想就是先递归分解数组,再合并数组。

将数组分解最小之后,然后合并两个有序数组,基本思路是比较两个数组的最前面的数,谁小就先取谁,取了后相应的指针就往后移一位。然后再比较,直至一个数组为空,最后把另一个数组的剩余部分复制过来即可。

如 设有数列{6,202,100,301,38,8,1}

初始状态:6,202,100,301,38,8,1

第一次归并后:{6,202},{100,301},{8,38},{1},比较次数:3;

第二次归并后:{6,100,202,301},{1,8,38},比较次数:4;

第三次归并后:{1,6,8,38,100,202,301},比较次数:4;

总的比较次数为:3+4+4=11;

逆序数为14;

python实现:

def merge_sort(alist):
    """
    递归分治序列
    :param alist:
    :return:
    """
    if len(alist) <= 1:
        return alist
    num = len(alist)//2
    left = merge_sort(alist[:num])
    right = merge_sort(alist[num:])
    return merge(left, right)  # 合并

def merge(left, right):
    """
    合并操作
    :param left:
    :param right:
    :return:
    """

    l, r = 0, 0
    result = []
    while l < len(left) and r < len(right):
        if left[l] < right[r]:  # 筛选排序将left与right最小元素按序加入新序列
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += left[l:]
    result += right[r:]
    return result

webp

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
将数组a中数据元素实现就地逆置的算法
给出将整型数组a中数据元素实现就地逆置的算法。所谓就地逆置,就是利用数组a原有空间来存放数组a中逆序排放后的各个数据元素。
180 0
【前端算法】JS实现数字千分位格式化
JS实现数字千分位格式化的几种思路,以及它们之间的性能比较
103 0
【前端算法】用JS实现快速排序
理解数组方法里面运用到的算法,splice 和 slice的区别
51 0
【前端算法】javaScript实现二分查找
如何使用JS实现一个合格的二分查找
81 0
【前端算法】链表和数组实现队列的区别
比较链表和数组实现队列的性能
81 0
【前端算法】两个栈实现一个队列
介绍栈和队列的区别,以及如何使用栈实现一个队列
49 0
一行代码解决LeetCode实现 strStr()使用JavaScript解题|前端学算法
一行代码解决LeetCode实现 strStr()使用JavaScript解题|前端学算法
62 0
Kalman算法C++实现代码(编译运行通过)
Kalman算法C++实现代码(编译运行通过)
85 0
一则有趣的算法题:两个栈实现一个队列
一则有趣的算法题:两个栈实现一个队列
41 0
C++ 实现KMP字符串匹配算法
C++ 实现KMP字符串匹配算法
46 0
+关注
python之战
专注python学习与应用擅长爬虫、web、全栈,专注RPA技术实施;(个人公号:Python之战)
文章
问答
视频
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
双剑合璧-Python和大数据计算平台的结合
立即下载
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
相关实验场景
更多