算法基础：归并排序（超详细）

归并排序

题目1：归并排序

给定你一个长度为 n 的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式
输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。

输出格式
输出共一行，包含 n 个整数，表示排好序的数列。

数据范围
1≤n≤100000
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5

#include
#include
#include

using namespace std;

const int N = 100010;

int q[N],tmp[N];

int n;

void merge_sort(int q[], int l, int r){
    
    if(l>=r) return;
    
    int mid = l+r >>1;
    
    merge_sort(q,l,mid)；
    merge_sort(q,mid+1,r);
    
    //i和j相当于一个双指针，指向当前需要排序的数组的两个部分。
    int i=l,j=mid+1;
    int k=0;
    while(i<=mid && j<=r){
        if(q[i]<=q[j])  tmp[k++] = q[i++];
        else  tmp[k++] = q[j++];
    }
    while(i<=mid)  tmp[k++] = q[i++];
    while(j<=r)   tmp[k++] = q[j++];
    
    //注意这里的l和r是相对于原始的q数组的位置，而tmp保存的值只是当前指针指向的这两个部分的排好序的值。
    for(int i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];
}

int main(){
    
    int n;
    cin>>n;
    
    for(int i=0;i<n;i++) scanf("%d", &q[i]);
    
    merge_sort(q,0,n-1);
    
    for(int i=0; i<n;i++) printf("%d ",q[i]);
    
    return 0;
    
}


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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

算法思想： 归并排序也是基于分治的思想，但是与快速排序不同的是，归并排序是先分治，再排序（先递归，再比较）。而快速排序是先排序，再分治（先比较，再递归）；从总体来说归并排序的计算是自底向上的，而快速排序的计算是自顶向下的。由于归并排序在排序的过程中对数组的划分是固定的（快速排序不是固定的，与选择的基准点有关），所以归并排序的复杂度是固定的。
复杂度分析：归并排序（Merge Sort）是一种典型的分治算法，其时间复杂度和空间复杂度如下：
时间复杂度：最好情况下，归并排序的时间复杂度为O(nlogn)；最坏和平均情况下，归并排序的时间复杂度也为O(nlogn)。
空间复杂度：归并排序的空间复杂度为O(n)，因为在合并过程中，需要额外的空间存储左右两个子序列的元素。
具体的分析过程如下：
1.归并排序首先将待排序序列均分为两个子序列，然后分别对这两个子序列进行排序，最后将排序好的子序列进行合并。这个过程可以递归进行，直到子序列的长度为1，此时可以认为子序列已经排好序。
2.在最好情况下，即待排序序列已经排好序时，每次递归的两个子序列都是有序的。这时，归并排序的时间复杂度为O(n)。因为无论序列长度为多少，都只需要进行一次合并操作。
3.在最坏和平均情况下，即待排序序列完全无序或部分有序时，每次递归的两个子序列都需要进行排序。这时，归并排序的时间复杂度为O(nlogn)。因为每次递归都需要将序列均分为两个子序列，然后对这两个子序列进行排序。这个过程可以看作是对元素数量的对数级别的递归调用。
在空间复杂度方面，由于归并排序需要额外的空间存储左右两个子序列的元素，因此空间复杂度为O(n)。

题目2：归并排序的应用-逆序对的数量

给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 ia[j]，则其为一个逆序对；否则不是。

输入格式
第一行包含整数 n，表示数列的长度。

第二行包含 n 个整数，表示整个数列。

输出格式
输出一个整数，表示逆序对的个数。

数据范围
1≤n≤100000，
数列中的元素的取值范围 [1,109]。

输入样例：
6
2 3 4 5 6 1
输出样例：
5

//在分治后的每一层合并中顺便求出逆序对数量是这个题想法的由来，归并排序分治我们求的是从小到
//大的顺序，我们所求的逆序对恰好是逆序数量，与归并排序不谋而合。


#include
#include
#include
#include

using namespace std;

const int N =100000;

int q[N],f[N];

long long  res=0;

long long  merge_sort(int l,int r){

    if(l>=r) return 0;

    int mid=(l+r)>>1;

    res=merge_sort(l,mid)+merge_sort(mid+1,r);

    int k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r){
        if(q[i]<=q[j]) f[k++]=q[i++];
        else{
        //当前i后面的数都比j大，而且每个数组段在排序的过程中都是排好序的（由更小的数组段合并来的），所以逆序数加上mid-i+1。
            res+=mid-i+1;
            f[k++]=q[j++];
        }
    }
    while(i<=mid) f[k++]=q[i++];
    while(j<=r) f[k++]=q[j++];

   for(int i=l,j=0;i<=r;i++,j++) q[i]=f[j];

   return res;
}


int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++) scanf("%d",&q[i]);

    merge_sort(0,n-1);

    printf("%lld",res);

    return 0;
}

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

算法思想：由于递归的过程中是由下向上的合并的过程，且合并的过程中的各个子序列都是排好序的。所以就可以根据这一性质来判断逆序对的数量。具体来说，归并排序是一种稳定的排序算法，即相同元素的位置是不会改变的，当靠前的排好序的子序列的元素比后面的元素要小（默认降序），那么当前子序列中后面的元素也都要比他小，所以逆序的数量res + = mid+1-l.