归并排序

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  结果如下图所示

3       算法代码

主要分为两个部分，一个是总体递归框架部分，一个是对两个子问题的merge问题。

3.1    总体框架部分

//注意递归的结束条件，即只有一个元素的时候，递归截止

typedef int ElemType;

void MergeSort(ElemTypeA[],int low, int high)
{
    if(low <high)//high与low的差为元素个数，当low<high，是表明有多余个元素，表明可以继续递归。
    {
       int mid = (low+high)/2;
 
       MergeSort(A,low, mid);
       MergeSort(A,mid+1, high);
       Merge(A,low, mid, high);
    }
}

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] <A[mid])
           H[k++] =A[low++];
       else
           H[k++] =A[mid++];
    }
    while(low <=m)//左半还有未合并完成的
       H[k++] =A[low++];
    while(mid <=high)//右半还有未合并完成的
       H[k++] =A[mid++];
 
    for(inti = k-1; i >=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 <iostream>
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] <A[mid])
           H[k++] =A[low++];
       else
           H[k++] =A[mid++];
    }
    while(low <=m)//左半还有未合并完成的
       H[k++] =A[low++];
    while(mid <=high)//右半还有未合并完成的
       H[k++] =A[mid++];
 
    for(inti = k-1; i >=0; --i,--high)
       A[high] =H[i];//将合并的集合复制回去
}
void MergeSort(ElemTypeA[],int low, int high)
{
    if(low <high)//high与low的差为元素个数，当low<high，是表明有多余个元素，表明可以继续递归。
    {
       int mid = (low+high)/2;
 
       MergeSort(A,low, mid);
       MergeSort(A,mid+1, high);
       Merge(A,low, mid, high);
    }
}
void LP_MergeSort(ElemTypeA[],int len)
{

    MergeSort(A, 0,len-1);
}
void PrintArray(ElemTypeA[],int len)
{
    for(inti = 0; i < len; ++i)
    {
       printf("%3d",A[i]);
    }
    printf("\n");
}
int main()
{
    ElemType A[] ={9,2,8,3,7,1,0,6};
    int len = 8;
 
    printf("beforeMergeSort, array is ");
    PrintArray(A,len);

    LP_MergeSort(A,len);
    printf(" afterMergeSort, array is ");
    PrintArray(A,len);
    return 0;
};

4.2     运行截图