归并排序

老师课件

思路：

采用二分的思想，把一个数组分为左边和右边两部分，我先把左边排好序，右边排好序，最后再将这里边合并就是了。思路就是这样子，那这这时候就有人问了，左边怎么排好序？右边又怎么排好呢？好问题，那我们继续来分析。

第一次分完之后，左边是不是有一段序列了，那我对这段序列排序，是不是同样分成左右两部分，然后继续分啊分，到最后是不是左右两边是不是只剩一个数了？一个数是不是相当于排好了序？好，那这时后我们是不是可以进行合并了呀。

然后，问题又来了，我得到了两个有序的序列，怎么把这两个有序的序列合成一个，并且最后合成的序列也是有序的呢？我们可以这样解决这个问题：

我们弄两个指针p1和p2 分别指向左边部分和右边部分，然后再搞一个额外的数组help，我们比较这两个指针所指的值，谁小就把谁指向的值存入help中，然后它们就向右走，同样，小的值就放到help中，直到最后把左部分和右部分的数全部放到help中，那我们得到的help数组是不是就是左右两边合并后的数组并且是有序？那这不就做到合并操作嘛！好，下面上代码：

代码

/* 合并操作 */
void merge(int arr[],int l,int mid ,int r){
    int p1=l,p2=mid+1;
    int help[r-l+1],i=0;
    while(p1<=mid && p2<=r){
        help[i++]=arr[p1]<=arr[p2]?arr[p1++]:arr[p2++];
    }
    /* 将没导完的数据导到help */
    while(p1<=mid){
        help[i++]=arr[p1++];
    }
    while(p2<=r){
        help[i++]=arr[p2++];
    }
    /* 将help数组拷贝回给arr,注意，合并的是l到r这个区间，并不是0-尽头 */
    for(int k=0;k<i;k++){
        arr[l+k]=help[k];
    }
}
/* 二分操作 */
void process(int arr[],int l,int r){
    if(l==r){
        return;
    }
    int mid = l+((r-l)/2);
    process(arr,l,mid);      //左边部分
    process(arr,mid+1,r);    //右边
    merge(arr,l,mid,r);      //合并
}
/* 归并排序 */
void merge_sort(int arr[],int n){
    process(arr,0,n-1);
}

时间复杂度分析

二分操作 \(T(\frac{n}{2})\)，process中的基础常数时间操作忽略，只看merge 操作，第一个while循环\(O(\frac{n}{2})\) ,第二和第三个循环只会执行其中的一个，复杂度也是\(O(\frac{n}{2})\)，最后一个循环为\(O(n)\) ，所以，最后的时间复杂度：

\(T(n)=2T(\frac{n}{2})+O(n)\)

应用master 公式，\(T(n)=O(n*\log{n})\)
该公式在时间复杂度中有给出来