快速排序

# include <iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N];
void qsort(int a[], int l, int r){// 通过
    if(l>=r)return ;
    int x = a[l+r>>1], i=l-1, j=r+1;
    while(i<j){
        while(a[++i]<x);
        while(a[--j]>x);
        if(i<j)swap(a[i],a[j]);
    }
    qsort(a, l, j);qsort(a,j+1,r);
}
void quick_sort(int a[], 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]);
    }
    quick_sort(a, l, j);//
    quick_sort(a, j+1, r);
}
void quick_sort(int a[], int l, int r){
    if (l >= r) return;
    int x = a[l+r+1>>1], i = l-1, j = r + 1;//边界不能取 l, 如[1,2]会死循环
    while(i < j){
        do i ++; while(a[i] < x);
        do j --; while(a[j] > x);
        if(i < j) swap(a[i], a[j]);
    }
    quick_sort(a, l, i - 1);//用i枢纽则必须不能取到左边界；j，右。
    quick_sort(a, i, r);
}
void quick_sort(int a[], int l,int r)//快速排序
{// 这个代码没办法对有很多重复元素的数组降低复杂度
	if(l>=r)return;
	swap(a[l], a[l+r>>1]);// 枢纽可以随机一个
	int base=a[l];//base的作用是进行划分后，使得所有在base左边的元素小于等于base，
	//所有在base右边的元素大于等于base 
	int i=l,j=r;
	while(i<j) // 指针 j 必须先动
	{
		while(i<j&&a[j]>=base) j--; //找到右边小于base的元素下标 
		
		while(i<j&&a[i]<=base) i++; //找到左边大于base的元素下标 
		
		if(i < j) swap(a[i],a[j]);//a[i]>base and a[j]<base，左右替换，使得a[i]<=base and a[j]>=base 
	}
	a[l]=a[i];//最后的替换 
	a[i]=base;
	// for(int i=0;i<n;i++) cout<<a[i]<<" "; cout << endl;
	quick_sort(a, l,i-1);
	quick_sort(a, i+1,r);
}
int main(){
    int n; cin>>n;
    for(int i=0; i< n;i++) cin>>a[i];
    quick_sort(a, 0, n-1);
    for(int i=0;i<n;i++)cout<<a[i]<<" ";
}

第k大的数

int quick_select(int l, int r, int k){
    if(l==r) return a[l];
    int x=a[l], i=l-1, j=r+1;
    while(i<j){
        while(a[++i]<x);
        while(a[--j]>x);
        if(i<j)swap(a[i], a[j]);
    }
    int sl = j-l+1; // 比当前枢纽a[j]小的元素的个数
    if(k <= sl) return quick_select(l, j, k);
    return quick_select(j+1, r, k-sl);//去掉比我小的sl个元素，变成第k-sl大
}

归并排序

#include<iostream>
using namespace std;
const int N = 100010;
int a[N], n;
void merge_sort(int a[], int l, int r){
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(a, l, mid), merge_sort(a, mid + 1, r);
    int i = l, j = mid + 1, w[N], k = 0;
    while(i <= mid && j <= r) {
        if (a[i] <= a[j]) w[k++] = a[i++];
        else w[k++] = a[j++];
    }
    while(i <= mid) w[k++] = a[i++];
    while(j <= r) w[k++] = a[j++];
    for(int k = 0, i = l; i <= r;) a[i++] = w[k++];
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    merge_sort(a, 0, n-1);
    for(int i=0;i<n;i++) cout<<a[i]<< " ";
}

逆序对的个数

#include <iostream>
using namespace std;

const int N = 100010;
int n, a[N];

typedef long long ll;

ll merge_sort(int l, int r){
    if(l >= r) return 0;
    int mid = l + r >> 1;
    ll res = merge_sort(l, mid) + merge_sort(mid+1, r);
    int i = l, j = mid + 1, w[N], k = 0;
    while(i <= mid && j <= r) {
        if (a[i] <= a[j]) w[k++] = a[i++];
        else {
            w[k++] = a[j++];
            res += mid - i + 1;
        }
    }
    while (i <= mid) w[k++] = a[i++];
    while (j <= r) w[k++] = a[j++];
    for(int k = 0, i = l; i <= r;) a[i++] = w[k++];
    return res;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    
    cout<<merge_sort(0, n-1)<<endl;
}

整数二分

有单调性可二分，没单调性的有时也可二分。二分的本质是边界，区间可被分为满足某性质和不满足某性质的两部分。

// 区间 [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; // 判定 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; // 判定 mid 是否满足性质
        else r = mid - 1;
    }
    return l;
}

Acwing:789 数的范围

# include<iostream>
using namespace std;

const int N = 100010;
int a[N];
int n, q;

int left(int a[], int x){
    int l = 0, r = n-1;
    while(l < r){
        int mid = l + r >> 1;
        if(a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return a[l] == x ? l:-1;
}
int right(int a[], int x){
    int l = 0, r = n - 1;
    while(l < r){
        int mid = l + r + 1 >> 1;
        if(a[mid] <= x) l = mid;
        else r = mid - 1;
    }
    return a[l] == x ? l: -1;
}
int main(){
    cin >> n >> q;
    for(int i = 0; i < n; i ++) cin >> a[i];
    while(q--){
        int k; cin >> k;
        int l = left(a, k), r = right(a, k);
        cout << l << " " << r << endl;
    } 
}

浮点数二分

double bsearch(double x){
    // 求平方根
    double l = 0, r = x;
    while(r - l > 1e-8){ // 或者直接迭代 100 次
        double mid = (l + r) / 2;
        if(mid * mid >= x) r = mid;
        else l = mid;
    }
    return l;
}

Q.E.D.