快速排序and归并排序

两者都是递归处理。

快速排序的原理是把$\le$某一个数和$>$的两类数分开来，可以用双指针来做，或者写几个辅助数组（可能MLE），然后递归。

归并排序则是先递归，然后把序列合并。

两者的复杂度都是$O(nlogn)$,但是归并排序较为稳定，快速排序不稳定，所以以后（我个人）还是写归并的好（虽然归并可能会MLE）。

还是sort香

快速排序代码：

void qs(int l,int r)
{
    if(l>=r) return;
    int x=a[(l+r)/2];
    int i=l-1;
    int j=r+1;
    while(i<j)
    {
        do i++;while(a[i]<x);
        do j--;while(a[j]>x);
        if(i<j) swap(a[i],a[j]);
    }
    qs(l,j);
    qs(j+1,r);
}

归并排序代码：

void ms(int l,int r)
{
    if(l>=r) return;
    int mid=l+r>>1;
    ms(l,mid),ms(mid+1,r);
    int k=1,i=l,j=mid+1;
    while(i<=mid&&j<=r)
    {
        if(a[i]<a[j]) t[k++]=a[i++];
        else t[k++]=a[j++];
    }
    while(i<=mid) t[k++]=a[i++];
    while(j<=r) t[k++]=a[j++];
    for(i=l,j=1;i<=r;i++,j++) a[i]=t[j];
}

先来看几道快速排序的题目

AcWing 785. 快速排序

模板题目

直接上$O(nlogn)$

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int a[N];
void qs(int l,int r)
{
    if(l>=r) return;
    int x=a[l+r>>1];
    int i=l-1,j=r+1;
    while(i<j)
    {
        do i++;while(a[i]<x);
        do j--;while(a[j]>x);
        if(i<j) swap(a[i],a[j]);
    }
    qs(l,j);
    qs(j+1,r);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d",&a[i]);
    qs(1,n);
    for (int i = 1; i <= n; i ++ ) printf("%d ",a[i]);
    return 0;
}

AcWing 786. 第k个数

模板题

排序后输出$a_k$

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n,k,a[N];
void qs(int l,int r)
{
    if(l>=r) return;
    int x=a[l+r>>1];
    int i=l-1,j=r+1;
    while(i<j)
    {
        do i++;while(a[i]<x);
        do j--;while(a[j]>x);
        if(i<j) swap(a[i],a[j]);
    }
    qs(l,j);
    qs(j+1,r);
}
int main()
{
    scanf("%d%d",&n,&k);
    for (int i = 1; i <= n; i ++ ) scanf("%d",&a[i]);
    qs(1,n);
    printf("%d",a[k]);
}

现在再来几道归并排序的题目

AcWing 787. 归并排序

模板题$O(nlogn)$
直接上

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N],t[N];
void ms(int l,int r)
{
    if(l>=r) return;
    int mid=l+r>>1;
    ms(l,mid),ms(mid+1,r);
    int k=1,i=l,j=mid+1;
    while(i<=mid&&j<=r)
    {
        if(a[i]<a[j]) t[k++]=a[i++];
        else t[k++]=a[j++];
    }
    while(i<=mid) t[k++]=a[i++];
    while(j<=r) t[k++]=a[j++];
    for(i=l,j=1;i<=r;i++,j++) a[i]=t[j]; 
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    ms(1,n);
    for(int i=1;i<=n;i++) printf("%d ",a[i]);
}

AcWing 788. 逆序对的数量

这道题目有点难

我们再来看一下模板，这一步我也有点晕，转载一下

首先我们给出逆序对的定义：
对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对。
重要的地方在于，一个元素可以不只是在一个逆序对中存在。如果 k > j > i 且 a[i] > a[j] > a[k]，那么这里
有两个含 a[i] 的逆序对，分别是 (a[i], a[j]) 和 (a[i], a[k]), a[i]是可以使用多次的。

那么第二步是分析问题，这里我们可以使用分治法解决问题。

我们将序列从中间分开，将逆序对分成三类：

两个元素都在左边；
两个元素都在右边；
两个元素一个在左一个在右；
因此这就是我们算法的大致框架：

计算逆序对的数量（序列）：
1. 递归算左边的；
2. 递归算右边的；
3. 算一个左一个右的；
4. 把他们加到到一起。

这个时候我们注意到一个很重要的性质，左右半边的元素在各自任意调换顺序，是不影响第三步计数的，因此我们可以数完就给它排序。这么做的好处在于，如果序列是有序的，会让第三步计数很容易。
如果无序暴力数的话这一步是O(n^2)的。

比如序列是这样的

4 5 6 | 1 2 3
当你发现 4 比 3 大的时候，也就是说右边最大的元素都小于左边最小的元素，那么左边剩下的5和6都必然比右边的所有元素大，因此就可以不用数5和6的情形了，直接分别加上右半边的元素个数就可以了，这一步就降低到了
O(n), 我们知道递归式 T(n) = 2T(n/2)+O(n) = O(nlogn)的，所以排序的成本是可以接受的，并且这一问题下，
可以很自然地使用归并排序。

作者：SOLORED
链接：https://www.acwing.com/solution/content/5508/
著作权归作者所有。我仅供转载。

void ms(int l,int r)
{
    if(l>=r) return;
    int mid=l+r>>1;
    ms(l,mid),ms(mid+1,r);
    int k=1,i=l,j=mid+1;
    while(i<=mid&&j<=r)
    {
        if(a[i]<a[j]) t[k++]=a[i++];
        else t[k++]=a[j++];//看这里，这里出现了逆序对，有mid-i+1个
    }
    while(i<=mid) t[k++]=a[i++];
    while(j<=r) t[k++]=a[j++];
    for(i=l,j=1;i<=r;i++,j++) a[i]=t[j];
}

代码就呼之欲出了

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n;
int a[N];
int t[N];
long long ms(int l,int r)
{
    if(l>=r) return 0;
    int mid=l+r>>1;
    long long res=ms(l,mid)+ms(mid+1,r);
    int k=1,i=l,j=mid+1;
    while(i<=mid&&j<=r)
    {
        if(a[i]<=a[j]) t[k++]=a[i++];
        else
        {
            t[k++]=a[j++];
            res+=mid-i+1;
        }
    }
    while(i<=mid) t[k++]=a[i++];
    while(j<=r) t[k++]=a[j++];
    for(i=l,j=1;i<=r;i++,j++) a[i]=t[j];
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    printf("%lld",ms(1,n));//十年OI一场空，不开long long见祖宗
}