快速排序

原理

  1. 设当前要排序数组中元素的下标为 p 到 r ，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。
  2. 然后，将数组以pivot分为左右2部分，依次递归地做与第1步相同的处理，直到分解到最小（子数组只有1或2个元素，此时可以简单地交换2个元素或直接返回即可完成该部分的排序）
  3. 初始的 p 和 r 为 0 和 n-1，n为数组总长度，待所有的分割的子数组完成操作后，整个数组就完成了排序。

和归并的比较

可以对比归并排序和快速排序：

  1. 归并是从下到上，先处理子问题，再合并；而快速则是从上到下的，先完成分区处理，再递归地解决子问题。
  2. 合并无法在原地完成，必须使用额外空间，因此归并是非原地排序；而快排可以实现原地的分区。
  3. 二者复杂度都是 O(nlogn)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>
int a[1000];
void quick_sort( int left, int right) {
	if (left >= right)
		return;
	int key = a[left], i = left, j = right, temp;
	//以最左边的元素为基准
	while (i < j) {
		while (a[j] >= key && i < j)
			--j;
		while (a[i] <= key && i < j)
			++i;
		if (i != j) { //两边交换法
			temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
	}
	a[left] = a[i];
	a[i] = key;
	quick_sort(left, i - 1);
	quick_sort( i + 1, right);
}
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
		scanf("%d", &a[i]);
	quick_sort( 0, n - 1);
	for (int i = 0; i < n; ++i)
		printf("%d ", a[i]);
	return 0;
}

大整数乘法

原理

由于计算机的限制，一些大数据无法直接相乘，可以将大数乘法分解，分而治之，变成小数乘法后再将结果合并为大数的乘法结果。

问题：
设有 x 和 y 两个大数，计算其乘积。

数学前提：
设 n=max(len(x),len(y))n=max(len(x),len(y)) 其中len(x)表示x的长度.
则可以做如下分解:
x=x1∗10n/2+x0x=x_1 * 10^{n/2} + x_0
y=y1∗10n/2+y0y=y_1 * 10^{n/2} + y_0
其中 x1x_1 和 y1y_1 是高位部分, x0x_0 和 y0y_0 是低位部分.
则容易知道以下等式（S）：

x∗y=(x1∗10n/2+x0)∗(y1∗10n/2+y0)=x1∗y1∗10n+x1∗y0∗10n/2+x0∗y1∗10n/2+x0∗y0=x1∗y1∗10n+((x1+x0)∗(y1+y0)−x1∗y1−x0∗y0)∗10n/2+x0∗y0x*y = (x_1 * 10^{n/2} + x_0)*(y_1 * 10^{n/2} + y_0) = x_1*y_1*10^n+x_1*y_0*10^{n/2}+x_0*y_1*10^{n/2}+x_0*y_0 = x_1*y_1*10^n+((x_1+x_0)*(y_1+y_0)-x_1*y_1-x_0*y_0)*10^{n/2}+x_0*y_0

计算内容

根据上述的分割，递归地（因为可能仍然是大数）计算：
(x1+x0)∗(y1+y0)(x_1+x_0)*(y_1+y_0)
x1∗y1x_1*y_1
x0∗y0x_0*y_0
然后将他们合并到S中即可解出。

复杂度

递推式可以表示为：
𝑇(𝑛) = 3𝑇(𝑛/2) + 𝑂(𝑛)
根据主定理解得：
𝑂(𝑛 𝑙𝑜𝑔23 ) ≈ 𝑂(𝑛 1.585)

矩阵乘法-Strassen算法

// 略…

最接近点对

  1. 将各点根据各点的x坐标排序
  2. 如果点数量小于等于3，直接计算即可
  3. 将点集分为左右2部分
  4. 递归地在左右2部分计算出最近距离d1和d2
  5. 取d=min(d1, d2)
  6. 在2子集的中间边界内，找出横跨边界的点对中最近的距离d3
  7. 取min(d, d3)作为最终结果

注意：算法的一个关键就是中间部分的处理，根据鸽巢原理可以大大优化算法，详见：
最邻近点对问题(Closest-Pair Problem)：二维的分治解法详解_closestpair算法-CSDN博客
平面最近点对 - OI Wiki

注：本文参考自课程ppt