归并排序

归并排序

老师课件

image-20211031173908243

思路:

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

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

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

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

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/* 合并操作 */
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})$

master 公式不会的请看这篇博文:{% post_link 算法基础/时间复杂度 时间复杂度 %}

0%