1.1 快排

AcWing 785. 快速排序

// 快速排序算法模板
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = q[l];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
        else break;
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

AcWing 786. 第k个数

int quick_sort(int q[],int l, int r, int k){
    if(l >= r) return q[l];
    int i = l - 1, j = r + 1,  x= q[l + 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]);
    }
    if(j -l + 1 >= k) return quick_sort(q, l, j,k);
    else return quick_sort(q, j +1, r, k -(j -l +1));
}

1.2 归并排序

归并排序是稳定 ，相对位置不变
快排不稳定

归并稳O(nlogn)

AcWing 787. 归并排序

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 i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r){
        if(q[i] <= q[j]) tmp[k ++] = q[i ++];
        else tmp[k ++] = q[j ++];
    }
    while(i <= mid) tmp[k ++] = q[i ++];
    while(j <= r) tmp[k ++] =q[j ++];
    for (int i = l, j = 0; i <= r; i ++, j ++) q[i] = tmp[j];

}

AcWing 788. 逆序对的数量

LL merge_sort(int q[], int l, int r){
    if(l >= r ) return 0;
    int mid = l + r >> 1;
    LL res = 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 ++];
        else {
            res += mid- i+ 1;
            tmp[k ++] = q[ j ++];
        }
    }
    while (i <= mid) tmp[k ++] = q[i ++];
    while (j <= r) tmp[k ++] = q[j ++];
    for(int i = l,j = 0; i <=r; i ++, j ++) q[i] = tmp[j];
    return res;

}

1.3 二分

整数二分：二分的本质是边界

AcWing 789. 数的范围

#include <iostream>

using namespace std;
const int N = 1e5 + 10;
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;
        }
    }
}

AcWing 790. 数的三次方根

#include <iostream>

using namespace std;

int main(){
    double x;
    cin >> x;
    double l = - 10000, r = 10000;
    while(r - l > 1e-8){
        double mid = (l + r) /2;
        if(mid * mid * mid >= x) r = mid;
        else l = mid;
    }

    printf("%lf", l);

}

六位小数，比较1e-8比较靠谱

AcWing 791. 高精度加法

vector<int> add(vector<int> &A, vector<int> &B){
    vector<int> C;
    int t = 0;
    for(int i = 0; i < A.size() || i < B.size(); i ++){
        if(i < A.size()) t += A[i];
        if(i < B.size()) t += B[i];
        C.push_back(t % 10);
        t = t/10;
    }

    if(t) C.push_back(1);


    return C;
}

AcWing 792. 高精度减法

#include <iostream>
#include <vector>

using namespace std;

bool cmp(vector<int> &A, vector<int> &B){
    if(A.size() != B.size()) return A.size() > B.size();

    for(int i = A.size()- 1; i >= 0; i --)
        if(A[i] != B[i]) return A[i] > B[i];

    return true;

}


vector<int> sub(vector<int> &A, vector<int> &B){
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i++){
         t = A[i] - t;
         if(i < B.size()) t -= B[i];
         C.push_back((t + 10) % 10);
         if ( t < 0) t= 1;
         else t = 0;
    }
    while(C.size()> 1 && C.back() == 0) C.pop_back();

    return C;
}

int main(){
    string a, b;
    cin >> a >>b;
    vector<int> A, B;
    vector<int> C;
    for (int i = a.size() - 1; i>= 0; i --) A.push_back(a[i]-'0');
    for (int i = b.size() - 1; i>= 0; i --) B.push_back(b[i]-'0');
    if(cmp(A, B)) C = sub(A, B);
    else C = sub(B, A), cout <<"-";


    for (int i = C.size() -1 ; i >= 0;i -- ) cout << C[i];

}