排序算法-归并排序

文章目录

• 基本思想
• 递归方法的实现
• 非递归方法的实现
• 归并排序的特性总结

基本思想

归并排序（MERGE-SORT）是建立在归并 *** 作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

将已经有序的子序列合并，得到完全有序的序列；
即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

总的来说，就是把对一个无序数组排序的问题转化为将两个有序数组排序成一个有序数组的问题。

下面是一次归并排序的流程图

递归方法的实现

通过对排序流程的了解，我们发现其实排序的过程大致可以分为两个部分。

首先需要对被排数据进行分割,直到把每组分割的只剩一个数据。

其次我们认为每组数据都是有序的，再让两个有序的数组合并成为一个有序的数组（可以使用选择排序的方法）

以上就是归并排序的递归方法实现过程，就是我们要先对数据进行分段，然后再对每一段进行排序，过程其实有点像二叉树的后序遍历。

非递归方法的实现

使用非递归的方法的主要思想其实与递归的类似，我们还是要想办法对数据进行分段，然后对每段进行排序，那么我们如何来对数据进行分段呢？

我们可以借用一个gep变量来完成对数据的分段。
我们假设第i段的起始终止下标为【i,i+gep-1】；第i+1段的起始结束下标为【i+gep,i+2*gep-1】，把数据分段后，我们再让gep乘2，然后继续分段，其分段的过程入下图

我们看后面分好的下标就可以发现通过这样的方法，我们分的段长度都只有一，第二次分段每段的长度为2，第三次分段每段长度为4，这样刚好就符合我们对归并分段的要求，而gep的值也就代表了每一段的长度。
有了分段方法，但是还有几个需要注意的特殊情况：

（1）最后两个小组归并时，最后一个小组不存在。
（2）最后两个小组归并时，最后一个小组存在，但是数量不够gep个
（3）最后两个小组归并时，不但最后一个小组不存在，第一个小组都不够gep个

先分析第一种情况，因为我们在归并时认为两个小组的都是有序的，那么如果第二个小组不存在，那第一个小组本身就是有序的，那这一部分就已经有序了，不用再进行归并排序，第三种情况与这种类似，所以第一和第三中情况都不需要对当前的部分进行归并了。

剩下就是第二种情况，最后一组存在但是数量不够，这样的话如果仍然按照前面的公式寻找第二组的数据话，就可能会出现越界的问题，所以我们需要对这种情况进行一下处理，如果发现最后一组的数据不够，我们就要调整一下最后一小组的结束下标，而它的长度虽然有变化，但是它任然是一个有序的部分，所以不会影响我们的归并，调整完成后继续归并即可。

以下是代码实现部分


以上就是归并排序的非递归实现方法

归并排序的特性总结

这里对归并排序的特性作一个大概的总结：

时间复杂度：O(N×㏒N)
空间复杂度：O(N)
稳定性:稳定

可以发现归并排序的效率还不错，并且排序时，如果我们碰到相同的值，让左边部分的哪一个排在前面，这样也能保证排序的稳定性。但是它有一个问题是O(N)的空间复杂度，这一点与其他算法相比就没有任何的优势了，可以说是最耗费空间的算法，但是归并排序的优势其实是对超大数据的排序。

我们的程序是在内存中运行的，当然我们写的排序算法也是在内存中对数据进行排序的，那么当我们对一组数进行排序时，首先我们要把这部分数据先加载到内存中，然后在运行我们的代码对他们进行排序。然而内存的大小是非常有限的，我们认为内存大概有4G的空间，里面还包含了内核使用的部分，剩下用户使用的部分还被分成了各种区（堆区，栈区，代码区等），而我们要排序的数据应该被加载到栈区，而栈区的大小又是非常有限的，假设我们的栈区可以让我们处理512M的数据（这也很大了，处理一般的数据足够了），当处理小于512M的数据时，任何一种排序算法都可以排，但是假如我们要对一个大小为4G的数据进行排序时怎么办呢？我们就可以使用归并排序。
以下是排序的过程图

刚刚的例子是4G的数据，其实任何大小的数据都可以使用这种方法。
我们还可以发现，其实我们在排序的时候，是在内存外的磁盘中处理的数据，所以我们才可以做到对如此大的数据进行排序，否侧在内存内是无论如何也无法做到排序这么大量的数据的，而这种排序方法称为外排序，而在内存中处理数据的排序成为内排序。

所以的排序算法中只有归并排序可以做到外排序，所以对超大数据进行排序时，一定要用到归并排序。