科代的救星——归并排序_【OI爱好者】

说好不提成绩的呢？！...

期末考试结束啦！相信除了笔者其他人都考得很好呢！

相信科代表们都会有一个烦恼：

拿到了全班成绩，怎么把它排序得出排名呢？

当然，在Excel上只要按一个键就能轻松实现

但你想知道强大的Office究竟是怎么实现的吗？

接下来的几篇，我们将详细介绍当今的几种主流排序算法。

它们各有优劣，也独具特色；它们的存在，架起了算法的世界。

今天我们就带大家了解一种排序算法——归并排序。

什么是归并

归并是这样的一个问题：

对于k个已经有序的序列，把其中的元素全部提取出来组成另一个新的有序序列。

归并分为二路归并、三路归并以至k路归并等。我们在这里只讨论二路归并。以下如果没有特殊说明，归并都是指二路归并。

（二路）归并事实上就是下图这样的一个过程：

归并的实现

有关归并的具体实现，目前最直观以及效率最高的算法是：

1.从剩余的原非空序列中的最小端取出每一个剩余序列的最小值；

2.计算出这些取出的值中的最小值；

3.把其中一个值为全局最小值的元素追加到新序列的最大端；

4.把追加到最大端的元素从原序列中删去；

5.如果还有剩余元素，返回步骤1.

我们用一张图简明地表现这一过程：

归并方法的正确性证明

归并排序

既然归并已经可以实现，那么现在我们要将归并应用到排序中。

试想我们要将序列
排成有序，我们取这个序列的中点

（为保证中点是一个合法下标序号，这里使用了向下取整符号）

先想办法使子区间
有序，再使子区间
有序，最后归并这两个子区间，于是整个序列有序。但是这样不会无限递归下去吗？

于是我们这里约定了边界条件，也就是使递归停止的条件。我们发现，如果一个序列长为1，那么这个序列就是有序的。所以求解需要分类讨论：

1°当序列长度等于1时，这个序列已经有序，停止求解；

2°当序列长度大于1时，使左右两个子区间有序后进行归并。

由于每次求解子问题时，序列长度都减小并且满足子序列不为空，所以最终都可以在边界条件停止求解，所以排序可以通过归并来进行。这样的排序被称为归并排序。这里使用二路归并则称为二路归并排序，相应的还有三路归并排序等。

单纯的文字不太直观，我们可以用这张图大致了解归并过程各个元素的位置变化：

归并方法的时间复杂度

我们设为长度为
的序列排序所需要的时间复杂度为
,用
表示
的增长级别相同。通过上面讲到的归并方法，归并成一个长度为
的有序序列的时间复杂度是
的，那么：

,

所以

.（想一想，为什么？）

小结

归并排序是一种常见的排序算法，时间复杂度低，具有广泛的应用。归并排序的时间复杂度是稳定的，不会随着初始序列的数据分布而变化（比如说快速排序虽然平均复杂度与归并排序一致，但是会出现算法退化的情况）。此外，它是稳定的排序算法，即原来多个相同关键字的记录经过排序后相对次序不变。归并排序的这些特性使其在很多领域都有独到的应用。