算法基础1—排序 二分

1.快速排序

给定你一个长度为$n$的整数数列。请你使用快速排序对这个数列按照从小到大进行排序。并将排好序的数列按顺序输出。

输入格式：输入共两行，第一行包含整数$n$。第二行包含$n$个整数（所有整数均在 $1∼10^9$ 范围内），表示整个数列。

输出格式：输出共一行，包含$n$个整数，表示排好序的数列。

数据范围$1≤n≤100000$

输入样例：

1
2
5
3 1 2 4 5

输出样例：

1
1 2 3 4 5

2.gif

基本思想：基于分治

  • 确定分界点：$q[l],q[(l+r)/2],q[r]$或者随机为$x$
  • 调整区间：第一个区间内均为$\le x$，第二个区间内均为$\ge x$
    • 开两个数组$a[\ ]$和$b[\ ]$
    • 对$q[l\sim r]$：$q[i]\le x\ $把$x$放入$a[\ ]$否则放入$b[\ ]$
    • 把$a[\ ]$和$b[\ ]$按照顺序重新放入$q[\ ]$中
  • 递归处理：递归的给左边排序，递归的给右边排序。
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
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N];
void quick_sort(int q[], int l, int r)
{
    if(l >= r) return;//看边界
     int i = l - 1, j = r + 1, x = q[l + r >> 1];//取分界点
    while(i < j){//进行迭代
        do i ++ ;while(q[i] < x);//左边界中如果小于x，则向后移动
        do j -- ;while(q[j] > x);//如果小于y，则向前移动
        if(i < j) swap(q[i], q[j]);//互换数据
    }
    quick_sort(q, l ,j);//对左右两端均使用快排
    quick_sort(q, j + 1 ,r);//对左右两端均使用快排
    
}
int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i ++) scanf("%d", &q[i]);
    quick_sort(q, 0, n - 1);
    for(int i = 0; i < n; i ++) printf("%d ", q[i]);
    return 0;
}

2.归并排序

给定你一个长度为$n$的整数数列。请你使用快速排序对这个数列按照从小到大进行排序。并将排好序的数列按顺序输出。

输入格式：输入共两行，第一行包含整数$n$。第二行包含$n$个整数（所有整数均在 $1∼10^9$ 范围内），表示整个数列。

输出格式：输出共一行，包含$n$个整数，表示排好序的数列。

数据范围$1≤n≤100000$

输入样例：

1
2
5
3 1 2 4 5

输出样例：

1
1 2 3 4 5

3.gif

核心：双指针+分治

  • 确定分界点$mid=(l+r)/2$
  • 递归排序$left,right$
  • 归并两个已经排好顺序的数组，合二为一（！）
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
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], tmp[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);
    //递归的求左侧和右侧
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
    	//如果q[i]比q[j]小，就把q[i]放入tmp中
        else tmp[k ++ ] = q[j ++ ];
    	//如果q[j]比q[i]小，就把q[j]放入tmp中
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    //如果左半边没有循环完，就把左半边放入tmp中
    while (j <= r) tmp[k ++ ] = q[j ++ ];
    //如果右半边没有循环完，就把右半边放入tmp中
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    merge_sort(a, 0, n - 1);
    for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);
    return 0;
}

3.整数二分

3.1二分概述

二分：整个数组可以划分为两部分，从某一点开始，右边全部满足某一性质，左边全都不满足某一性质。

本质：找到一个性质，划分两部分。

二分模板一共有两个，分别适用于不同情况。
算法思路：假设目标值在闭区间$[l, r]$中， 每次将区间长度缩小一半，当$l = r$时，我们就找到了目标值。

版本1

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

  • 寻找中间值$mid=(l+r)/2$
  • 检查中间值点是否满足性质$check(mid)$
1
2
3
4
5
6
7
8
9
10
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;
}

3.2数的范围

给定一个按照升序排列的长度为$n$的整数数组，以及$q$个查询。对于每个查询，返回一个元素$l$的起始位置和终止位置（位置从0开始计数）。如果数组中不存在该元素，则返回 -1 -1。

输入格式

第一行包含整数$n$和$q$，表示数组长度和询问个数。第二行包含$n$个整数（均在$1\sim10000$范围内），表示完整数组。接下来$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
39
40
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int q[N];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    while (m -- )
    {
        int x;
        scanf("%d", &x);

        int l = 0, r = n - 1;
        //二分起始坐标
        while (l < r)
        {
            int mid = l + r >> 1;
            if (q[mid] >= x) r = mid;
            else l = mid + 1;
        }
		//如果不存在
        if (q[l] != x) cout << "-1 -1" << endl;
        //寻找右边界
        else
        {
            cout << l << ' ';
            int l = 0, r = n - 1;
            while (l < r)
            {
                int mid = l + r + 1 >> 1;
                if (q[mid] <= x) l = mid;
                else r = mid - 1;
            }
            cout << l << endl;
        }
    }
    return 0;
}

3.3 浮点数二分

开平方：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
using namespace std;
int main()
{
    double x;
    cin >> x;
    double l = 0,r = x;
    while(r - l > 1e-8)
    {
        //寻找中间分点
        double mid = (l + r) / 2;
        //计算是否符合条件
        if (mid * mid >= x) r = mid;
        else l = mid;
    }
    printf("%lf\n" , l);
    return 0;
}