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
相关文章
|
11月前
|
JSON 区块链 数据格式
Python实现一个简单的区块链
本文介绍如何用Python实现一个简单的区块链。
390 0
|
11月前
|
存储 数据安全/隐私保护 计算机视觉
python 实现pacs功能 推送下拉影像
python 实现dcmtk关联pacs功能 推送下拉影像
198 0
python 实现pacs功能 推送下拉影像
|
11月前
|
算法 大数据 Python
Leedcode 每日一练 搜索二维矩阵Ⅰ Python实现
Leedcode 每日一练 搜索二维矩阵Ⅰ Python实现
95 2
Leedcode 每日一练 搜索二维矩阵Ⅰ Python实现
|
11月前
|
前端开发 Python
Leecode加法题目3个 每日练习 Python实现
Leecode加法题目3个 每日练习 Python实现
72 0
Leecode加法题目3个 每日练习 Python实现
|
11月前
|
iOS开发 Python
Python实现微信消息连续发送
Python实现微信消息连续发送
Python实现微信消息连续发送
|
11月前
|
Python
Python print() 打印两个 list ,实现中间换行
Python print() 打印两个 list ,实现中间换行
|
11月前
|
Python
python实现微信小游戏“飞机大战”
python实现微信小游戏“飞机大战”
python实现微信小游戏“飞机大战”
|
11月前
|
Python
Python分分钟实现图书管理系统(含代码)
Python分分钟实现图书管理系统(含代码)
212 0
|
11月前
|
JSON 算法 数据安全/隐私保护
Python:使用PyJWT实现JSON Web Tokens加密解密
Python:使用PyJWT实现JSON Web Tokens加密解密
209 0
|
12月前
|
Python
Python实现因子分析(附案例实战)
Python实现因子分析(附案例实战)
675 0
Python实现因子分析(附案例实战)
推荐文章
更多