排序

1.快速排序

#include 
using namespace std;
const int N = 2e5 + 10;
int a[N], n, s, e;
void quickSort(int l, int r){
	int key = a[(l + r) / 2], i = l, j = r;
	while (i <= j){
		while (a[i] < key)
			i++;
		while (a[j] > key)
			j--;
		if (i <= j)
			swap(a[i++], a[j--]);
	}
	if (l < j) quickSort(l, j);
	if (i < r) quickSort(i, r);
}
int main(){
	cin >> n;
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	quickSort(1, n);
	for (int i = 1; i <= n; i++)
		cout << a[i] << " \n"[i == n];
	return 0;
}

模板题：https://www.luogu.com.cn/problem/P1177

2.归并排序

#include 
using namespace std;
#define LL long long
const int N = 1e5 + 10;
LL a[N], tmp[N], n;
void mergeSort(LL l, LL r){
	if (l >= r) return;
	LL mid = (l + r) >> 1, i = l, j = mid + 1, cnt = 0;
	mergeSort(l, mid);
	mergeSort(mid + 1, r);
	while (i <= mid || j <= r)
		if (j > r || (i <= mid && a[i] <= a[j]))
			tmp[cnt++] = a[i++];
		else
			tmp[cnt++] = a[j++];
	for (LL k = 0; k < r - l + 1; k++)
		a[l + k] = tmp[k];
}
int main(){
	cin >> n;
	for (int i = 1; i <= n; i++)
		scanf("%lld", &a[i]);
	mergeSort(1, n);
	for (int i = 1; i <= n; i++)
		cout << a[i] << " \n"[i == n];
	return 0;
}

应用：

求解逆序对

https://www.luogu.com.cn/problem/P1908 题解：
https://codeforces.com/contest/1591/problem/D 题解：