归并排序
Written By lpstudy, A man ofstriving for life.Please mark the deviation if you copy it.
1 排序描述
归并排序是一种重要的递归排序排序思想。它将一个大的问题划分成两个子问题，然后分别对两个小点的子问题进行求解，对求解后的结果合并后即为原大问题的解。由于这个是递归的，于是原来一个很大的问题，就被一点一点的拆分，最后拆分成最简单的情况，可以直接求解，然后将一点点的简单的情况逐个合并，最后即为所得。说着有些复杂，不过代码实现由于使用了递归，看起来就非常整洁明了了。
void MergeSort(整个A)
{
if(满足条件)//这实际是递归的进行条件，也可以反过来看是递归的结束条件
{
MergeSort(A的前一半); //子问题，A的前一半
MergeSort(A的后一半); //子问题，A的后一半
Merge(A的前一半，A的后一半);//两个子问题的解的合并
}
}
2 存储结构
此排序算法可以直接数组存储。下面举例说明排序过程，一共有8个元素。
l 首先将8个元素的问题分解两个4个元素的问题。即9 2 83 和 7 1 0 6
l 然后对于前面4个的问题，即9 2 8 3，同样继续分解为两个2个元素的问题，即分解为92 和 8 3。
l 再次对于前面的小小子问题92，继续分解为两个子问题9和2
l 再再次对于前面的小小小子问题9，它只有一个元素，故而肯定是有序就不用排序了。
l 开始合并过程，将9和2两个子问题合并，排序成2，9；8和3两个子问题合并为3，8
l 继续合并2,9和3,8，合并成2,3,9,8.另外的一半同样合并为0，1，6，7
l 继续合并两个子问题得到最终的结果0,1,2,3,6,7,8,9
l 结果如下图所示
| 索引 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
| 元素值 |
9 |
2 |
8 |
3 |
7 |
1 |
0 |
6 |
| 第1趟 |
2 |
9 |
3 |
8 |
1 |
7 |
0 |
6 |
| 第2趟 |
2 |
3 |
8 |
9 |
0 |
1 |
6 |
7 |
| 第3趟 |
0 |
1 |
2 |
3 |
6 |
7 |
8 |
9 |
3 算法代码
主要分为两个部分，一个是总体递归框架部分，一个是对两个子问题的merge问题。
3.1 总体框架部分
//注意递归的结束条件，即只有一个元素的时候，递归截止
typedef int ElemType;
void MergeSort(ElemTypeA[],int low, int high)
{
if(low
3.2 合并函数
//两个子问题的合并问题。
void Merge(ElemType A[], int low,int mid, int high)
{
//将两个有序表A[low-> mid]和A[mid+1 -> high] 合并。
//需要借助第三个表帮助合并，为了简单起见，我直接定义一个局部静态数组充当暂存数据
const int MAX_SIZE = 9999;
static ElemType H[MAX_SIZE];//辅助合并表
int m = mid++;
int k = 0;//合并后的H表的索引
while(low <=m && mid<= high)
{
if(A[low]
=0; --i,--high)
A[high] =H[i];//将合并的集合复制回去
}
3.3 时间复杂度
由算法过程可以看出，每一个子问题合并为O(n)的级别，每一个子问题为T(n/2),故而中时间为T(n) = 2*T(n/2) + O(n)。这个时间复杂度为O(nlgn)，而且它是一个稳定排序。
对于T(n) = a*T(n/b) + f(n)的形式，算法导论中有证明
如果f(n) <, 则T(n) = O()
如果f(n)=, 则T(n) = O(*lgn)
如果f(n)>, 则T(n) = O() 其中当n趋近于无穷时，a*f(n/b)/ f(n) < 1
举例来说：
T(n)= 2T(n/2) + O(1) 其中b=a=2，故而属于第1种情况，T(n) = O(n)
T(n)= 2T(n/2) + O(n) 其中b=a=2，故而属于第2种情况，T(n) = O(n*lgn)
T(n)= 2T(n/2) + O(n*n) 其中b=a=2，故而属于第3种情况，T(n) = O(n*n)
4 执行代码和截图
4.1 完整执行代码
#include
using namespacestd;
typedef int ElemType;
//两个子问题的合并问题。
void Merge(ElemType A[], int low,int mid, int high)
{
//将两个有序表A[low-> mid]和A[mid+1 -> high] 合并。
//需要借助第三个表帮助合并，为了简单起见，我直接定义一个局部静态数组充当暂存数据
const int MAX_SIZE = 9999;
static ElemType H[MAX_SIZE];//辅助合并表
int m = mid++;
int k = 0;//合并后的H表的索引
while(low <=m && mid<= high)
{
if(A[low]
=0; --i,--high) A[high] =H[i];//将合并的集合复制回去 } void MergeSort(ElemTypeA[],int low, int high) { if(low
4.2 运行截图
