分享

图解python归并排序

 昵称70813452 2020-07-11

基本思想

归并排序(merge-sort)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案合并在一起,即分而治之)。

分治类似于二分的思想,打个不恰当的比喻,我们知道常见的冒泡,简单插入排序的时间复杂度都是O(n2)O(n^2)O(n2),并且如果原数组的有序程度越高,这些简单排序的实际时间复杂度就会越小。对于一个长度为nnn的无序数组,如果一分为二成两个子数组,对每个子数组排序,那么时间为O((n/2)2)=O(n2/4)O((n/2)^2)=O(n^2/4)O((n/2)2)=O(n2/4),然后由于子数组有序那么合并的时间也不需要很长,因此总体来讲分治的思想就能降低时间复杂度。

如下:
在这里插入图片描述
将数组切分成至多两个元素的一个个子数组,对每个子数组比较排序之后然后与依次合并,这样的形式也很像完全二叉树,下面是针对一个任意无序数组的动图演示。

项目 方法
ir43Q 0wJUO8030
y4zDL 2006.02.06 15-30-42
EV50I 今日头条
0iw64 2006-10-18 05:28:45
rU091 XhUG89702

在这里插入图片描述

代码

# python3
def mergesort(seq):
    """归并排序"""
    if len(seq) <= 1:
        return seq
    mid = len(seq) / 2  # 将列表分成更小的两个列表
    # 分别对左右两个列表进行处理,分别返回两个排序好的列表
    left = mergesort(seq[:mid])
    right = mergesort(seq[mid:])
    # 对排序好的两个列表合并,产生一个新的排序好的列表
    return merge(left, right)

def merge(left, right):
    """合并两个已排序好的列表,产生一个新的已排序好的列表"""
    result = []  # 新的已排序好的列表
    i = 0  # 下标
    j = 0
    # 对两个列表中的元素 两两对比。
    # 将最小的元素,放到result中,并对当前列表下标加1
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result

seq = [5,3,0,6,1,4]
print('排序前:',seq)
result = mergesort(seq)
print('排序后:',result)

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。
    转藏 分享 献花(0

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多