归并排序算法过程图解,归并排序算法过程图解merge

排序算法（二）:递归排序之归并排序

? ? 递归就是函数调用本身，和高中数学的数学归纳法类似。当在求一个数组的第n项的时候，有两种方式，第一种就是根据各种公式，求通项公式，第二种，就是数学归纳法，发现数据项前后两项的规律。可以这么说，递归只要知道开始的特殊情况，知道过程是如何展开的。（递推：相反使用一个循环来实现，但有的时候递推有一定难度，不过可以使用栈来实现消除递归，这么说，一些编译器都是用栈来实现递归的）

????归并排序的原理是，合并两个有序的数组。两个有序数的合并相对较为简单， 通常遍历一遍就可以合并。因此只要保证两个数组是有序，然后进行一次合并，就得到一个有序数组。那么，上述的过程已经发现了，假设要对一个数组进行排序，那么可以将其一分为二，得到两个数组，那么如何保证这两个数组有序的。这里已经很明显的，问题又回到开头，也就是递归（调用函数本身）。递归不能只是关注过程，也要关注（边界问题），不然可能会陷入死循环，甚至坐标越界。现在的（边界）就是，何时，数组不可再分？很显然，就是也就是数组小于二。换而言之，就是数组大于一是调用函数本身。

? ??????

归并排序的算法原理是什么？

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，归并排序将两个已排序的表合并成一个表。

归并排序基本原理

通过对若干个有序结点序列的归并来实现排序。

所谓归并是指将若干个已排好序的部分合并成一个有序的部分。

归并排序基本思想

设两个有序的子序列(相当于输入序列)放在同一序列中相邻的位置上：array[low..m]，array[m + 1..high]，先将它们合并到一个局部的暂存序列 temp (相当于输出序列)中，待合并完成后将 temp 复制回 array[low..high]中，从而完成排序。

在具体的合并过程中，设置 i，j 和 p 三个指针，其初值分别指向这三个记录区的起始位置。合并时依次比较 array[i] 和 array[j] 的关键字，取关键字较小（或较大）的记录复制到 temp[p] 中，然后将被复制记录的指针 i 或 j 加 1，以及指向复制位置的指针 p加 1。重复这一过程直至两个输入的子序列有一个已全部复制完毕(不妨称其为空)，此时将另一非空的子序列中剩余记录依次复制到 array 中即可。

什么叫归并排序？

可以运用分而治之方法来解决排序问题，该问题是将n 个元素排成非递减顺序。分而治之方法通常用以下的步骤来进行排序算法：若n 为1，算法终止；否则，将这一元素集合分割成两个或更多个子集合，对每一个子集合分别排序，然后将排好序的子集合归并为一个集合。

假设仅将n 个元素的集合分成两个子集合。现在需要确定如何进行子集合的划分。一种可能性就是把前面n- 1个元素放到第一个子集中（称为A），最后一个元素放到第二个子集里（称为B）。按照这种方式对A递归地进行排序。由于B仅含一个元素，所以它已经排序完毕，在A排完序后，只需要用程序2 - 1 0中的函数i n s e r t将A和B合并起来。把这种排序算法与I n s e r t i o n S o r t（见程序2 - 1 5）进行比较，可以发现这种排序算法实际上就是插入排序的递归算法。该算法的复杂性为O (n 2 )。把n 个元素划分成两个子集合的另一种方法是将含有最大值的元素放入B，剩下的放入A中。然后A被递归排序。为了合并排序后的A和B，只需要将B添加到A中即可。假如用函数M a x（见程序1 - 3 1）来找出最大元素，这种排序算法实际上就是S e l e c t i o n S o r t（见程序2 - 7）的递归算法。

假如用冒泡过程（见程序2 - 8）来寻找最大元素并把它移到最右边的位置，这种排序算法就是B u b b l e S o r t（见程序2 - 9）的递归算法。这两种递归排序算法的复杂性均为(n2 )。若一旦发现A已经被排好序就终止对A进行递归分割，则算法的复杂性为O(n2 )（见例2 - 1 6和2 - 1 7）。

上述分割方案将n 个元素分成两个极不平衡的集合A和B。A有n- 1个元素，而B仅含一个元素。下面来看一看采用平衡分割法会发生什么情况： A集合中含有n/k 个元素，B中包含其余的元素。递归地使用分而治之方法对A和B进行排序。然后采用一个被称之为归并（ m e rg e）的过程，将已排好序的A和B合并成一个集合。

考虑8个元素，值分别为[ 1 0，4，6，3，8，2，5，7 ]。如果选定k = 2，则[ 1 0 , 4 , 6 , 3 ]和[ 8 , 2 , 5 , 7 ]将被分别独立地排序。结果分别为[ 3 , 4 , 6 , 1 0 ]和[ 2 , 5 , 7 , 8 ]。从两个序列的头部开始归并这两个已排序的序列。元素2比3更小，被移到结果序列；3与5进行比较，3被移入结果序列；4与5比较，4被放入结果序列；5和6比较，.。如果选择k= 4，则序列[ 1 0 , 4 ]和[ 6 , 3 , 8 , 2 , 5 , 7 ]将被排序。排序结果分别为[ 4 , 1 0 ]和[ 2 , 3 , 5 , 6 , 7 , 8 ]。当这两个排好序的序列被归并后，即可得所需要的排序序列。

二路归并排序

归并排序是通过“归并”操作完成排序的，将两个或者多个有序子表归并成一个子表。

归并排序是“分治法”的一个非常典型的应用，同事它也是递归算法的一个好的实例。它将问题分成一些小的问题然后递归求解，而治就是把分阶段的答案拼起来。

即：将该算法截为两段,对前后两段应用该算法均可得到一个有序序列,这是就有了两个有序序列,再使用该算法就最终得到一个有序序列而递归终点是当分段内只有一个元素时,显然就是有序序列了,就可以返回。