排序和二分

Created2021-01-25Updated2021-02-03

排序和二分

排序和二分

快速排序

一、算法思想：分治

什么是分治？

分治，字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。在计算机科学中，分治法就是运用分治思想的一种很重要的算法。分治法是很多高效算法的基础，如排序算法（快速排序，归并排序），傅立叶变换（快速傅立叶变换）等等。将父问题分解为子问题同等方式求解，这和递归的概念很吻合，所以在分治算法通常以递归的方式实现(当然也有非递归的实现方式)。分治算法的描述从字面上也很容易理解，分、治其实还有个合并的过程：

  • 分(Divide)：递归解决较小的问题(到终止层或者可以解决的时候停下)
  • 治(Conquer)：递归求解，如果问题够小直接求解。
  • 合并(Combine)：将子问题的解构建父类问题

当求解一个问题规模很大很难直接求解，但是规模较小的时候问题很容易求解并且这个问题并且问题满足分治算法的适用条件，那么就可以使用分治算法。

二、步骤：

  1. 确定分界点： x = a[l] , a[mid] , a[r] , 随机也可

  2. 调整区间：将区间分为两个部分，使得左区间所有的数都小于等于x，右区间所有的数都大于等于x即可。 （关键部分）

  3. 递归的分别给左右两个区间继续做相同的处理，当左边和右边分别都是有序的时候，整个区间就有序了

    时间复杂度：期望复杂度O(n logn) ，最坏复杂度 O(N)

第二步如何实现？

一、一个非常朴素而暴力的做法：

  1. 设原数组为q，开两个新的数组 a[],b[];

  2. 将q中小于等于基准数x的所有数（左区间的数）都存入a中，大于等于的存入b中，分别对a，b进行处理之后，再将处理好的数重新存入q中即可。

    （很不优雅，而且需要用额外的空间，但是会比较好写）

二、一个优雅的做法：

  1. 选择一个基准数之后，使用两个变量i，j作为“指针”，从区间的两端不断往区间的中间走。

  2. 往中间走的过程中，一旦遇到左指针指向的数大于等于x，右指针指向的数小于等于x的情况，那么就交换这两个数，那么这两个数的位置就放好了，继续找剩下的数，直到i，j相遇为止，相遇之后，区间就被分为了小于等于x和大于等于x的两个区间。

  3. 正确性证明：在这种做法中，我们可以保证在任何时刻，i左边的数一定都小于等于x（否则会被交换），同理，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
39
40
#include<iostream>
using namespace std;
int a[100050];
void q_sort(int l,int r)
{
    if(l>=r)return ;
    int x=a[(l+r)>>1],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]);
    }
    //这里的写法是无论如何都会移至少一位，因此左右区间应该先分别加减一
    //同时 do while 和 while 有区别，需注意
    q_sort(l,j);
    q_sort(j+1,r);
}
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    q_sort(1,n);
    for(int i=1;i<=n;i++)
    {
        cout<<a[i]<<" ";
    }
    return 0;
}

四、例题

  1. 洛谷 P1177 快速排序

归并排序

一、算法思想：分治

与快速排序相比，分治方法不同：

  1. 快速排序是找基准数，排好后再递归两边。

  2. 归并排序是先确定分界点，递归排序左边和右边，再把两个有序的数组合并成一个有序的数组（merge，合二为一）

二、步骤

  1. 确定分界点：mid=(l+r)/2;

  2. 递归排序左边和右边，使左右两个区间都变得有序 （ 时间复杂度O(log N) ）

  3. 归并，将两个有序的数组合并为一个有序的数组 （ 关键步骤: 时间复杂度O(N) ）

三、代码

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
#include<iostream>
#include<cstdio>
using namespace std;
int a[100050];
int t[100050];
int n;
void merge_sort(int l,int r)
{
    if(l>=r)return ; //当前区间里只有一个或者没有数，那么显然就不用排序了
    
    int mid = (l+r)>>1;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    
    int cnt=1,i=l,j=mid+1;//i,j分别指向左右两个区间
    while(i<=mid and j<=r)
    {
        if(a[i]<=a[j])t[cnt++]=a[i++];
        else t[cnt++]=a[j++];
    }
    while(i<=mid)t[cnt++]=a[i++];
    while(j<=r)t[cnt++]=a[j++];
    //归并的过程，存到一个临时数组中
    for(i=l,j=1;i<=r;i++,j++)
    {
        a[i]=t[j];
    }
    //把临时数组里的存回去
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    merge_sort(1,n);
    for(int i=1;i<=n;i++)
    {
        cout<<a[i]<<" ";
    }
    return 0;
}

四、例题

  1. 洛谷 P1177 快速排序

  2. 洛谷 P1908 逆序对

    朴素做法：O(n^2) 直接枚举，显然过不了，考虑优化到O(n logn) –> 数据结构/分治

    优化：

    1. 分治：基于归并排序。在归并排序中的归并（merge）部分，我们会比较左右两区间当前的最小的数。在右区间的第一个数比左区间更小的情况下，就一定会产生若干组逆序对。

      因此可用类似归并排序的方法来解决：

      1. 左半边内部逆序对数量：merge_sort(l,mid);
      2. 右半边内部逆序对数量：merge_sort(mid+1,r);
      3. 一个在左边，一个在右边的逆序对（归并，merge）

      由归并排序的性质可知，[l,mid] , [mid+1,r]两个区间内的序列都是有序的，因此每次产生逆序对的数量是 mid+1-i ; mid+1表示右区间的第一个数（第2,3…个数都会逐渐变为第一个数），对左区间会从i开始产生逆序，i之前的是顺序的。

  【原理可通过画图来进一步理解，详见洛谷P1908题解】
  1. 数据结构：树状数组（略）
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
//P1908 逆序对 归并排序做法
#include<iostream>
#include<cstdio>
using namespace std;
const int N=500020;
int n;
int a[N],t[N];
long long ans=0;
void merge_sort(int l,int r)
{
    if(l>=r)return ; 
    int mid=(l+r)>>1;
    merge_sort(l,mid);
    merge_sort(mid+1,r);

    int cnt=1,i=l,j=mid+1;
    while(i<=mid and j<=r)
    {
        if(a[i]<=a[j])t[cnt++]=a[i++];
        else 
        {
            t[cnt++]=a[j++];
            ans+=mid+1-i;
        }
    }
    while(i<=mid)t[cnt++]=a[i++];
    while(j<=r)t[cnt++]=a[j++];
    for(i=l,j=1;i<=r;i++,j++)
    {
        a[i]=t[j];
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    merge_sort(1,n);
    cout<<ans;
    return 0;
}

二分

一、模板

使用二分法时，注意边界条件会带来的种种奇怪的问题

二分模板一共有两个，分别适用于不同情况。

算法思想：

假设目标值在闭区间 [l, r] 中， 每次将区间长度缩小一半，当l = r时，我们就找到了目标值。

版本1

当我们将区间 [l, r] 划分成 [l, mid] 和 [mid + 1, r] 时，其更新操作是 r = mid 或者 l = mid + 1 ，计算mid时不需要加1。

代码：

1
2
3
4
5
6
7
8
9
10
11
12

int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

版本2

当我们将区间[l, r]划分成 [l, mid - 1] 和 [mid, r] 时，其更新操作是 r = mid - 1 或者 l = mid ，此时为了防止死循环，计算mid时需要加1。

代码：

1
2
3
4
5
6
7
8
9
10
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

经过测试发现，加减法的运算优先级居然高于位运算，因此 l+r 那里可以不用加括号啦

二、应用

使用二分的背景：

对于一个单调的序列，使得某种性质在区间的右边是一定满足的，在区间的左边是一定不满足的，即这种性质将区间一分为二。这时候可以使用二分法找到区间的边界点。

例子：使 a值最大的 最小k值

三、STL

在C++的STL库中有一些常用的基于二分原理的方便好用的函数：

lower_bound (起始地址，结束地址，要查找的数值) 返回的是 第一个大于等于待查找数值 出现的位置。

upper_bound (起始地址，结束地址，要查找的数值) 返回的是 第一个大于待查找数值 出现的位置。

binary_search (起始地址，结束地址，要查找的数值) 返回的是是否存在这么一个数，是一个bool值。

注意：使用二分查找的前提是数组有序。

详细用法见：CSDN

四、例题

  1. AcWing 789 数的范围

  2. 洛谷 P2249 查找

  3. 洛谷 P2678 跳石头（NOIP2015 提高组） P1182 数列分段

**1. acwing 789 **

给定一个按照升序排列的长度为n的整数数组，以及 q 个查询。

对于每个查询，返回一个元素k的起始位置和终止位置（位置从0开始计数）。

如果数组中不存在该元素，则返回“-1 -1”。

输入格式

第一行包含整数n和q，表示数组长度和询问个数。

第二行包含n个整数（均在1~10000范围内），表示完整数组。

接下来q行，每行包含一个整数k，表示一个询问元素。

输出格式

共q行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回“-1 -1”。

数据范围

1≤n≤100000
1≤q≤10000
1≤k≤10000

输入样例：

1
2
3
4
5
6 3
1 2 2 3 3 4
3
4
5

输出样例：

1
2
3
3 4
5 5
-1 -1

代码：

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;
int a[100050];
int n,q;
int main()
{
    cin>>n>>q;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    while(q--)
    {
        int k;
        cin>>k;
        int l=0,r=n-1,mid;
        while(l<r)
        {
            mid=(l+r)>>1;
            if(a[mid]>=k)r=mid;
            else l=mid+1;
        }//找到第一个>=k的数, 此时性质：>=k
        if(a[l]!=k)cout<<"-1 -1"<<endl;
        else 
        {
            cout<<l<<" ";
            r=n-1;
            while(l<r)
            {
                mid=(l+r+1)>>1;
                if(a[mid]<=k)l=mid;
                else r=mid-1;
            }//找到最后一个=k的数, 此时性质：<=k(他左边的全部<=k)
            cout<<r<<endl;
        }
    }
    return 0;
}