Acwing 快排归并整理笔记

2023-01-10 150

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Acwing 快排归并整理笔记

快速排序：

快排板子：分治思想

1.确定分界点（x = a[l+r>>1]），这么做是为了避免有序的情况下，子问题规模依旧较大的问题（如果有序且分界点取在首个，那么数组被分为长度1和n-1）

2.调整区间，使得第一个区间<=x,第二个区间>=x；

3.递归两个区间

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

归并排序

1：确定分界点

2：递归

3：归并merge（注意可能一条链子输完了另一条还没有输完的情况）

归并板子：

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e5+10;
int tmp[N];//临时容器
int a[N];
void mergesort(int l,int r,int a[])
{
    if (l>=r) return ;
    int mid = l+r>>1;//划分区间
    mergesort(l,mid,a);
    mergesort(mid+1,r,a);//递归排序
    int i = l,j = mid+1,k =0;
    while (i<=mid&&j<=r)//双指针
    {
        if (a[i]<=a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }
    while (i<=mid) tmp[k++] = a[i++];
    while (j<=r) tmp[k++] = a[j++];//收尾
    for (int i = l,j = 0;j<k;j++,i++) a[i] = tmp[j];//复制到到原数组
}
int main()
{   
    int n;
    scanf("%d",&n);
    for (int i = 0;i<n;i++) scanf("%d",&a[i]);
    mergesort(0,n-1,a);
    for (int i = 0;i<n;i++) printf("%d ",a[i]);
    return 0;
}

经典例题：逆序对的数量：acwing788

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

输入样例：

1. 6
2. 2 3 4 5 6 1

输出样例：

逆序对分成三块，前两块ans加上函数自身的递归，第三块先排序再累加；

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const LL N = 1e5+10;
LL a[N],tmp[N];
LL mergesort(LL l,LL r,LL a[])
{   
    if (l>=r) return 0;
    LL mid = l+r>>1;
    LL ans = 0;
    ans+=mergesort(l,mid,a)+mergesort(mid+1,r,a);
    LL i = l,j = mid+1,k = 0;
    while (i<=mid&&j<=r)
    {
        if (a[i]<=a[j]) tmp[k++] = a[i++];
        else
        {
            tmp[k++] = a[j++];
            ans += mid-i+1;
        }
    }
    while (i<=mid) tmp[k++] = a[i++];
    while (j<=r)   tmp[k++] = a[j++];
    for (LL i = 0,j = l;i<k;i++,j++)  a[j] = tmp[i];
    return ans;
}
int main()
{
    LL n;
    scanf("%ld",&n);
    for (int i = 0;i<n;i++) scanf("%ld",&a[i]);
    LL ans = mergesort(0,n-1,a);
    printf("%ld",ans);
    return 0;
}