基础算法

快速排序

void quick_sort(int q[], int l, int r) {
	if (l == r)return;

	int i = l - 1, j = r + 1, x = q[l + r >> 1];
	loop:
	while (q[++i] < x);
	while (q[--j] > x);
	if (i < j) {
		swap(q[i], q[j]);
		goto loop;
	}
	quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

归并排序

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, tmp[r - l + 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 (i = l, j = 0; j < k; i++, j++)q[i] = tmp[j];
}

整数二分

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 左边界
int bsearch_1(int l, int r) {
	while (l < r) {
		int mid = l + r + 1 >> 1;
		if (check(mid)) l = mid;
		else r = mid - 1;
	}
	return l;
}

// 右边界
int bsearch_2(int l, int r) {
	while (l < r) {
		int mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	return l;
}