快速排序

https://www.acwing.com/problem/content/787/

这个是模板，一定要背熟。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5 + 15;
int n;
int a[N];

void quick_sort(int a[], int l, int r) {
    //递归终止条件
    if(l >= r) return ;

    //将大于x的放在x左边，小于x的放在x右边
    int i = l - 1, j = r + 1, x = a[l + 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]);
    }

    //递归处理左右两边，逐渐将区间缩小
    //保证q[l, j] <= x, q[j + 1, r] > x，再将区间缩小
    quick_sort(a, l, j);
    quick_sort(a, j + 1, r);
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    quick_sort(a, 1, n);
    for(int i = 1; i <= n; i++) cout << a[i] << " ";
    return 0;
}

https://www.acwing.com/problem/content/788/

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5 + 15;
int n, k;
int a[N];

int quick_sort(int a[], int l, int r) {
    //递归终止条件
    if(l >= r) return a[k];

    //将大于x的放在x左边，小于x的放在x右边
    int i = l - 1, j = r + 1, x = a[l + 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]);
    }

    //递归处理左右两边，逐渐将区间缩小
    //下标就是第几小的数
    if(k <= j) return quick_sort(a, l, j);
    else return quick_sort(a, j + 1, r);
}

int main() {
    cin >> n >> k;
    //这里下标从1开始更好
    for(int i = 1; i <= n; i++) cin >> a[i];
    cout << quick_sort(a, 1, n) << endl;
    return 0;
}

归并排序

https://www.acwing.com/problem/content/789/

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5 + 15;
int n;
int a[N], tmp[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, k = 0;
    while(i <= mid && j <= r) {
        if(a[i] <= a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }

    //将剩下的小区间都加入大区间中
    while(i <= mid) tmp[k++] = a[i++];
    while(j <= r) tmp[k++] = a[j++];

    //替换到原数组中
    for(i = l, k = 0; i <= r; ) a[i++] = tmp[k++];
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    merge_sort(a, 1, n);
    for(int i = 1; i <= n; i++) cout << a[i] << " ";
    return 0;
}

https://www.acwing.com/problem/content/790/

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 1e5 + 15;
int n;
LL ans;
int a[N], tmp[N];

LL merge_sort(int a[], int l, int r) {
    if(l >= r) return 0;

    int mid = l + r >> 1;
    merge_sort(a, l, mid);
    merge_sort(a, mid + 1, r);

    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r) {
        if(a[i] <= a[j]) tmp[k++] = a[i++];
        else {
            //因为左右两个小区间是单调递增的，所以若a[i] > a[j]，则a[i, mid] > a[j]
            ans += mid - i + 1;
            tmp[k++] = a[j++];
        }
    }

    while(i <= mid) tmp[k++] = a[i++];
    while(j <= r) tmp[k++] = a[j++];
    for(i = l, k = 0; i <= r;) a[i++] = tmp[k++];
    return ans;
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    cout << merge_sort(a, 1, n) << endl;
    return 0;
}