图文讲解归并排序_归并排序生活中例子

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

介绍

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

采用分治法:

• 分割：递归地把当前序列平均分割成两半。
• 合并：在保持元素顺序的同时将上一步得到的子序列合并到一起（归并）。

图解算法

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

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

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

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