基础算法(排序 & 查找)

快速排序、归并排序、整数二分查找、浮点数二分查找

快速排序

主要思想是分治:

1. 确定分界点
2. 调整范围
3. 递归处理左右两段

代码:

#include <iostream>
using namespace std;

const int N = 1e6+10;

int n,q[N];

void quick_sort(int q[],int l,int r) {
    // 左右重合则返回
    if (l >= r)
        return;
    // 选取分界点和双指针
    int x = q[(l+r+1)/2],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,i-1);
    quick_sort(q,i,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;
}

归并排序

主要思想是分治，快排以一个数来分界，归并以中间来分，并且先递归两边

1. 确定分界点
2. 递归排序左右
3. 归并，合二为一

归并排序是稳定的

#include <bits/stdc++.h>

using namespace std;

const int N = 10e6+10;

int n,q[N],temp[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]) temp[k++] = q[i++];
        else temp[k++] = q[j++];
    }
    
    // 将未循环完的数直接拼接
    while (i <= mid) temp[k++] = q[i++];
    while (j <= r) temp[k++] = q[j++];
    for (i=l,j=0;i<=r;i++,j++)
        q[i] = temp[j];
}


int main(void) {
    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]);
    }   
}

二分查找(整数)

按照某种性质将区间一分为二，分成一半满足和另一半不满足

#include <iostream>
using namespace std;

const int N = 10e5 + 10;

int n,m,q[N];

// 检查x是否具有某种性质
bool check(int x) {
    // .....
} 

// 第一种: 区间[l,r]划分为[l,mid]和[mid+1,r]
int bsearch(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(int l,int r) {
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

二分查找(浮点)

浮点数的二分查找要关注精度

bool check(double x) {
    // .....
} 

double bsearch(double l,double r) {
    const double eps = 1e-6;
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}