排序与二分

排序

  • 快速排序
  • 归并排序

1.快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int x=q[l+r >>1];//确定分界点，这里q[]未必要找中点
    int i = l - 1, j = r + 1;
    while (i < j)
    {
        do i++; while (q[i] < x);
        do j--; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

2.归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void merge_sort(int a[],int l,int r)
{
    if(l>=r) return;
    int mid= l+r >>1;//确定分界点，一定得找中点
    merge_sort(a,l,mid);
    merge_sort(a,mid+1,r);
    int k=0;
    int i=l,j=mid+1;
    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;i<=r;i++,j++)
    a[i]=tmp[j];
}

逆序对的数量

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
#include <iostream>
using namespace std;
const int N=1e5+10;
long long merge_sort(int a[],int l,int r)
{
    if(l>=r) return 0;
    int mid=l+r>>1;
    long long res=merge_sort(a,l,mid)+merge_sort(a,mid+1,r);
    int i=l,j=mid+1,k=0;
    int b[N];
    while(i<=mid&&j<=r)
    {
        if(a[i]<=a[j])
        b[k++]=a[i++];
        else
        {
            res+=mid-i+1;
            b[k++]=a[j++];
        }
    }
    while(i<=mid)
    b[k++]=a[i++];
    while(j<=r)
    b[k++]=a[j++];
    for(int i=l,j=0;i<=r;i++,j++)
    a[i]=b[j];
    return res;
}
int main()
{
    int n;
    cin>>n;
    int a[N];
    for(int i=0;i<n;i++)
    scanf("%d",&a[i]);
    long long ans=merge_sort(a,0,n-1);
    cout<<ans;
}

二分

1
2
3
4
5
6
7
8
9
10
int l=-1,r=N;
while(l+1!=r)
{
    int mid=l+r>>1;
    if(isblue(mid))
        l=m;
    else
        r=m;
}
return l or r;

例题 acwing

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
#include <iostream>
using namespace std;
const int N=1e5+10;
int main()
{
    int n,q;
    cin>>n>>q;
    int a[N];
    for(int i=0;i<n;i++)
    scanf("%d",&a[i]);
    while(q--)
    {
        int x;
        cin>>x;
        int l=-1,r=n;
        while(l+1!=r)
        {
            int mid=l +r >>1;
            if(a[mid]<x)//isblue1
            l=mid;
            else
            r=mid;
        }
        if(a[r]==x) cout<<r;
        else cout<<-1;
        l=-1,r=n;
        while(l+1!=r)
        {
            int mid=l+r>>1;
            if(a[mid]<=x)//isblue2
            l=mid;
            else
            r=mid;
        }
        if(a[l]==x)
        cout<<" "<<l<<endl;
        else
        cout<<" "<<-1<<endl;
    }
}