基础算法(一)

排序
- 快排
- 归并排序
二分
- 整数
- 浮点数
学习要点
- 主要思想
- 背过
  - 思想理解，快速默写(重要)
  - 用题目检验背过
    - 重复刷题3-5遍

快速排序—分治

确定分界点q[l]，q[(lr)/2]，q[r]，随机
☆调整区间：使得小于分界点的数在左边，大于的在右边
递归处理左右两段
- 方法一(暴力)
  1. a[], b[]
  2. q[l~r]
    - q[i] ≤ x x→a[]
    - q[i] ≥ x x→b[]
  3. a[] → q[], b[] → q[]
- 方法二(优雅)
  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


#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]; //i，j为两个指针，x是分界点，这里的指针之所以往两边一位，是因为后面的写法中指针首先是要向中间移动一位。
    while (i < j)
    {
        do i ++ ; while (q[i] < x); //先移动一次i，如果q[i]小于分界点再继续移动
        do j -- ; while (q[j] > x); //先移动一次j，如果q[i]小于分界点再继续移动
        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;
}

归并排序—分治

找中点作为分界点：mid=(l+r)/2
递归排序左边和右边
☆归并，合二为一
- 用两个指针分别指向两个有序队列的开头，再定义一个新的数组记录答案，此时两个指针所指的数分别都是它们当前所在区间最小的数，比较这两个数的大小，较小的数就是原数组中最小的数，此时把这个数先放入新的数组，并把该指针向后移动一位，再次比较大小，重复以上操作直至一个指针先到达末尾，另一个指针之后所剩的数直接按序插入新数组末尾。
- 一个排序算法是稳定的是指，在排完序之后，原序列的两个相同数的位置不发生改变。
代码模板,双指针算法

 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


#include <iostream>

using namespace std;

const int N = 100010;

int n;
int q[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; //i,j是两个指针，k表示tmp中已经存在多少数
    while (i <= mid && j <= r) //i小于左半边的边界，j小于右半边的边界
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ]; //把较小的数放入tmp。++是先赋值再自增
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ]; //循环之后如果有剩下的数把两边有剩下的数再放入tmp
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j]; //把tmp中的数在放回q
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++) scanf("%d", &q[i]);

    merge_sort(q, 0, n-1);

    for (int i = 0; i < n; i++) printf("%d ", q[i]);
    
    return 0;
}

二分排序

整数二分：有单调性的话一定可以二分，没有单调性的话有可能可以二分。二分的本质是在区间上定义了某种性质，该性质在某一半边上满足，在另一半上不满足，使得把区间一分为二，二分就可以寻找这个性质的边界。
1. mid = (l + r + 1)/2,if(check(mid)),这里mid+1是因为c++向下取整，不+1可能会死循环
  - ture [mid, r], l = mid;
  - false [l, mid-1], r = mid - 1.
2. mid = (l + r)/2,if(check(mid))
  - ture [l, mid], r = mid;
  - false [mid + 1, r], l = mid + 1.
3. 代码模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


//区间[l, r]被划分成[l， mid]和[mid + 1, r]时使用：
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;
}

//区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
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;
}

浮点数二分

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


bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求，一般比要求的精度高两位
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}