图文讲解归并排序

在日常生活中有很多排序例子。比如说排队,就是按照时间的先后顺序;医院就医,紧急情况下会按照病情的严重程度;高考录取通常是按照分数的高低。从这些例子中似乎看不出排序算法的必要性。事实上并不是,就说高考的问题吧,全省的考生排名,假如全省有30万考生,该如何高效的排名呢?这就需要排序算法了。

介绍

归并排序(英语:Merge sort),是创建在归并操作上的一种有效的排序算法,效率为O(n\log n)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行1

采用分治法:
* 分割:递归地把当前序列平均分割成两半。
* 合并:在保持元素顺序的同时将上一步得到的子序列合并到一起(归并)。

图解算法

看完上面的定义,如果你感到有点懵,那就对了本文就是写给你的。我们通过图文来详细地介绍算法的流程。算法的核心只有4个字分割合并

假定我们对下面的序列,按照从小到大进行排序。

94, 45, 82, 33, 25, 59, 94, 65, 23

当然你很快地手动就能完成排序任务,但30万个数字你可能就会崩溃了。还是先来看这个例子,先将这个序列平均分割。一共有9个数字,取中间位置是4.5,取整的结果为4。分成两个子序列,前4个元素和后5个元素,然后分别对两个子序列递归操作,直到子序列只有一个元素为止。

归并排序-分

上面的步骤完成了分割,接下来开始合并了。最小的两个子序列是94和45,于是合并这两个子序列,得到序列[45, 94],另外的子序列是[33, 82],于是合并这两个子序列就得到左半部分[33, 45, 82, 94]。

归并排序中

这里元素较少,你可能并没有看清楚,就得到了左半部分有序子序列(前4个元素)。同样的操作我们得到后面5个元素的有序子序列,最后来合并这两个子序列。下文会详细说明。

[33, 45, 82, 94]
[23, 25, 59, 65, 94]

合并的过程都是一样的,下面gif动图清楚地演示了两个子序列的合并过程。(由于受公众号的限制,无法给出完成的演示)。完成的演示可以看后面的视频。

归并排序部分

参考代码

下面是用Python实现的归并排序算法的代码,仅供参考:

import typing as t

def sort(data: t.List[int]):
    """
    sort data
    """
    if len(data) <= 1:
        return data
    mid = len(data) // 2 
    left = sort(data[:mid])
    right = sort(data[mid:])
    return merge(left, right)

def merge(left: t.List[int], right: t.List[int]):
    """
    merge two list
    """
    i = 0 
    j = 0 
    ret = []
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            ret.append(left[i])
            i += 1
        else:
            ret.append(right[j])
            j += 1

        if i == len(left):
            ret.extend(right[j:])

        if j == len(right):
            ret.extend(left[i:])
    return ret

if __name__ == '__main__':
    d = [45, 94, 33, 82, 25, 59, 94, 65, 23]
    data = sort(d)
    print(data)


  1. https://zh.wikipedia.org/wiki/归并排序 ↩︎
关注机器学习和算法的码农,喜欢编程和读书
文章已创建 72

发表评论

电子邮件地址不会被公开。

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部