【算法】归并排序

• 2020 年 8 月 20 日
• 筆記
• mergesort, 归并, 归并排序, 快排, 算法

目录结构：

1. 简介

归并排序（MergeSort） 和快排的思想有相似之处。都是采用分治的思想，也就是，首先在一个数组中选择一个基准点，把数组分成两半，然后再对每一半再进行排序，递归直到所有数据都排好序。归并排序取分割点都是在数组的最中间，而且归并的过程也是采用了一个额外的数组变量来周转实现的。

首先先用C语言实现一个归并排序的过程。

是不是上面的代码不太好理解，别担心，下面笔者制作了一张gif图片，可以更加形象理解归并排序的过程。

2. 归并排序的时间复杂度

上面讨论了归并排序的实现过程和理论基础，接下来继续讨论归并排序的时间复杂度。归并排序和快速排序相似，接下来深入分析一下归并排序的时间复杂度，由于归并排序每次取的都是数列最中间的位置，于是我们可以得出如下的表达式：

T(n)  = T(n/2) + T(n/2) + n

这个表达式和快排最优情况下的表达式一样，这里我就不再解一遍了，详情请移步快速排序最优时间复杂度。 解上面表达式最终可以得到时间复杂度为： n logⁿ. 

因为归并排序总是取的最中间的位置，所以无论排序的数列是什么样的，数列的排序都只有一种情况。换句话说，归并排序的最差，最优，平均时间复杂度都是O(n logⁿ)。

3. 归并排序的空间复杂度

 上面讨论了时间复杂度，接下来讨论空间复杂度，这里的空间复杂度就比较简单了，因为整个算法只声明了一个额外的变量 temp_array ，大小为n。所以总的空间使用的空间，就是temp_array所占用的空间 加上 递归时压入栈的空间，也就是 n + logⁿ, 因此归并的空间复杂度就是O(n).

4. 总结

这篇文章写的比较短，主要是省略了归并排序时间复杂度的推算，因为它和 快排最优情况下的时间复杂度推算 是一样的。而归并的空间复杂度也是比较简单的。最后，归并排序是一种稳定的算法，而快排是一种不稳定的算法（比如：1140，如果基准点选首元素，那么最终的结果第一个1和第二个1就会互调位置，因此不稳定）。在选择归并和快排的时候，需要综合它们的时间复杂度，空间复杂度 和 稳定性 再做选择。