排序算法6---归并排序算法

归并排序算法采用的是分治算法,即把两个(或两个以上)有序表合并成一个新的有序表,即把待排序的序列分成若干个子序列,每个子序列都是有序的,然后把有序子序列合并成整体有序序列,这个过程也称为2-路归并.注意:归并排序的一种稳定排序,即相等元素的顺序不会改变.

归并排序之递归实现：

#include <stdio.h>

#define MAXSIZE 9  /* 用于要排序数组中元素个数最大值，可根据需要修改 */
typedef struct
{
    int r[MAXSIZE+1];        /* 用于存储要排序数组，r[0]用作哨兵或临时变量 */
    int length;            /* 用于记录顺序表的长度 */
}SqList;

/* 交换L中数组r的下标为i和j的值 */
void swap(SqList *L,int i,int j) 
{ 
    int temp=L->r[i]; 
    L->r[i]=L->r[j]; 
    L->r[j]=temp; 
}

void print(SqList L)
{
    int i;
    for(i=1;i<=L.length;i++)
        printf("%3d,",L.r[i]);
    printf("
");
}

/* 归并排序********************************** */

/* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] */
void Merge(int SR[], int TR[], int i, int m, int n){
    int j,k,l;
    for(j=m+1,k=i; i<=m && j<=n; k++){
        if(SR[j] < SR[i]){
            TR[k]=SR[j++];
        }else TR[k]=SR[i++];
    }
    if(i<=m){
        for(l=0; l <= m-i; l++){
        TR[k+l]=SR[i+l];    /* 将剩余的SR[i..m]复制到TR */
        }
    }
    if(j<=n){
        for(l=0; l <= n-j; l++){
        TR[k+l]=SR[j+l];    /* 将剩余的SR[j..n]复制到TR */
        }
    }
}

/* 递归法 */
/* 将SR[s..t]归并排序为TR1[s..t] */
void Msort(int SR[], int TR1[], int s, int t){
    int m;
    int TR2[MAXSIZE+1];
    if(s==t) TR1[s]=SR[s];
        else {
            m=(s+t)/2;                /* 将SR[s..t]平分为SR[s..m]和SR[m+1..t] */
            Msort(SR,TR2,s,m);        /* 递归地将SR[s..m]归并为有序的TR2[s..m] */
            Msort(SR,TR2,m+1,t);    /* 递归地将SR[m+1..t]归并为有序的TR2[m+1..t] */
            Merge(TR2,TR1,s,m,t);    /* 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] */
        }
}

/* 归并排序********************************** */
void MergeSort(SqList * L){
    Msort(L->r, L->r, 1, L->length);
}

int main(){
    SqList L;
    int num[10] = {9,5,3,2,4,6,1,7,8,9};    
    for(int i=0; i<10; i++){
        L.r[i]=num[i];
    }//注意给数组赋值的方法
    L.length=9;
    //归并排序
    MergeSort(&L);
    print(L);
    return 0;
}

归并排序时间复杂度分析：

1》归并排序的步骤如下：

Divide: 把长度为n的输入序列分成两个长度为n/2的子序列。

Conquer: 对这两个子序列分别采用归并排序。

Combine: 将两个排序好的子序列合并成一个最终的排序序列。

2》时间复杂度：

总时间=分解时间+解决问题时间+合并时间。分解时间就是把一个待排序序列分解成两序列，时间为一常数，时间复杂度o(1).解决问题时间是两个递归式，把一个规模为n的问题分成两个规模分别为n/2的子问题，时间为2T(n/2).合并时间复杂度为o（n）。总时间T(n)=2T(n/2)+o(n).这个递归式可以用递归树来解，其解是o(nlogn).此外在最坏、最佳、平均情况下归并排序时间复杂度均为o(nlogn).从合并过程中可以看出合并排序稳定。

用递归树的方法解递归式T(n)=2T(n/2)+o(n)：

归并排序及其时间复杂度分析 - 珑儿 - 顾影自怜

这是一个递推公式（Recurrence），我们需要消去等号右侧的T(n)，把T(n)写成n的函数。其实符合一定条件的Recurrence的展开有数学公式可以套，这里我们略去严格的数学证明，只是从直观上看一下这个递推公式的结果。当n=1时可以设T(1)=c₁，当n>1时可以设T(n)=2T(n/2)+c₂n，我们取c₁和c₂中较大的一个设为c，把原来的公式改为：

归并排序及其时间复杂度分析 - 珑儿 - 顾影自怜

这样计算出的结果应该是T(n)的上界。下面我们把T(n/2)展开成2T(n/4)+cn/2（下图中的(c)），然后再把T(n/4)进一步展开，直到最后全部变成T(1)=c（下图中的(d)）：

归并排序及其时间复杂度分析 - 珑儿 - 顾影自怜

把图(d)中所有的项加起来就是总的执行时间。这是一个树状结构，每一层的和都是cn，共有lgn+1层，因此总的执行时间是cnlgn+cn，相比nlgn来说，cn项可以忽略，因此T(n)的上界是Θ(nlgn)。

如果先前取c₁和c₂中较小的一个设为c，计算出的结果应该是T(n)的下界，然而推导过程一样，结果也是Θ(nlgn)。既然T(n)的上下界都是Θ(nlgn)，显然T(n)就是O(nlgn)。

空间复杂度：

由于归并排序在归并过程中需要与原始记录序列同样的存储空间存放结果以及递归时深度为logn的栈空间，因此空间复杂度为O(n+logn).

参考：【1】http://blog.csdn.net/bluetjs/article/details/52485920

【2】http://xwrwc.blog.163.com/blog/static/46320003201141582544245/