归并排序
题目1：归并排序
给定你一个长度为 n 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤100000
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
#include<iostream>
#include<cstring>
#include<algorithm>
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;
}
算法思想： 归并排序也是基于分治的思想，但是与快速排序不同的是，归并排序是先分治，再排序（先递归，再比较）。而快速排序是先排序，再分治（先比较，再递归）；从总体来说归并排序的计算是自底向上的，而快速排序的计算是自顶向下的。由于归并排序在排序的过程中对数组的划分是固定的（快速排序不是固定的，与选择的基准点有关），所以归并排序的复杂度是固定的。
复杂度分析：归并排序（Merge Sort）是一种典型的分治算法，其时间复杂度和空间复杂度如下：
时间复杂度：最好情况下，归并排序的时间复杂度为O(nlogn)；最坏和平均情况下，归并排序的时间复杂度也为O(nlogn)。
空间复杂度：归并排序的空间复杂度为O(n)，因为在合并过程中，需要额外的空间存储左右两个子序列的元素。
具体的分析过程如下：
1.归并排序首先将待排序序列均分为两个子序列，然后分别对这两个子序列进行排序，最后将排序好的子序列进行合并。这个过程可以递归进行，直到子序列的长度为1，此时可以认为子序列已经排好序。
2.在最好情况下，即待排序序列已经排好序时，每次递归的两个子序列都是有序的。这时，归并排序的时间复杂度为O(n)。因为无论序列长度为多少，都只需要进行一次合并操作。
3.在最坏和平均情况下，即待排序序列完全无序或部分有序时，每次递归的两个子序列都需要进行排序。这时，归并排序的时间复杂度为O(nlogn)。因为每次递归都需要将序列均分为两个子序列，然后对这两个子序列进行排序。这个过程可以看作是对元素数量的对数级别的递归调用。
在空间复杂度方面，由于归并排序需要额外的空间存储左右两个子序列的元素，因此空间复杂度为O(n)。
题目2：归并排序的应用-逆序对的数量
给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。
输入格式
第一行包含整数 n，表示数列的长度。
第二行包含 n 个整数，表示整个数列。
输出格式
输出一个整数，表示逆序对的个数。
数据范围
1≤n≤100000，
数列中的元素的取值范围 [1,109]。
输入样例：
6
2 3 4 5 6 1
输出样例：
5文章来源：https://uudwc.com/A/dbEL8
//在分治后的每一层合并中顺便求出逆序对数量是这个题想法的由来，归并排序分治我们求的是从小到
//大的顺序，我们所求的逆序对恰好是逆序数量，与归并排序不谋而合。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
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;
}
算法思想：由于递归的过程中是由下向上的合并的过程，且合并的过程中的各个子序列都是排好序的。所以就可以根据这一性质来判断逆序对的数量。具体来说，归并排序是一种稳定的排序算法，即相同元素的位置是不会改变的，当靠前的排好序的子序列的元素比后面的元素要小（默认降序），那么当前子序列中后面的元素也都要比他小，所以逆序的数量res + = mid+1-l.文章来源地址https://uudwc.com/A/dbEL8
