分治算法

分治算法的核心思想就是“分而治之”。将一个规模为n的问题分解为划分成 n 个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，最后进行合并即可得到原规模问题的解。

分治算法的性质让其很适合用递归的编程技巧来实现。有如下几步：

  1. 分解：先将原问题拆分，例如下标边界的分割，直到分解到最小。
  2. 解决：递归向下解决各个子问题，如果问题规模达到最小，则直接求解即可。
  3. 合并：递归完成后在上层合并为整个问题的解。

分治算法必须满足以下几个条件：

  1. 问题缩小到一定程度可以直接求解。
  2. 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
  3. 各个子问题的解可以合并为更大规模问题解。
  4. 分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

二分查找

二分查找需要满足如下条件：

  1. 数据使用顺序表（数组）存储
  2. 数据必须有序，一般从小到大
  3. 数据量太小并不适合使用二分查找
  4. 数据量太大也不适合，主要是因为一个超大的顺序表对内存的要求过高，可能无法存储

代码实现：二分查找模板 | WAHAHA’s blog

归并排序

将待排序数组进行二分，对每一个分组同样不断进行二分，分解到底部后，从小往大再逐渐重新合并，在合并的同时依次按顺序选择合并的值以达到排序的作用。

递推公式：merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))

终止条件：p >= r 不用再继续分解

性质：

  1. 归并排序是否稳定取决于merge函数，可以保证值相同的元素，在合并前后的先后顺序不变，所以归并排序是稳定的。
  2. 时间复杂度为O(nlogn)
  3. 由于递归时，堆栈会不断地创建（压栈）和销毁（出栈），因此临时空间不会超过n个数据的大小（不考虑程序实现的额外空间），空间复杂度为O(n)，而不是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
34
35
36
37
38
#include <stdio.h>
#include <stdlib.h>
void merge(int a[], int left, int mid, int right) {
	int i = left, j = mid + 1, k = 0;
	int* b = (int*)malloc(sizeof(int) * (right - left + 1));
	while (i <= mid && j <= right) {
		if (a[i] <= a[j])
			b[k++] = a[i++];
		else
			b[k++] = a[j++];
	}
	while (i <= mid)
		b[k++] = a[i++];
	while (j <= right)
		b[k++] = a[j++];
	for (i = left, k = 0; i <= right; ++i)
		a[i] = b[k++];
	free(b);
}
void merge_sort(int a[], int left, int right) {
	//5(0-4)->3(0-2)|2(3-4)
	if (left == right)
		return;
	int mid = (right + left) / 2;
	merge_sort(a, left, mid);
	merge_sort(a, mid + 1, right);
	merge(a, left, mid, right);
}
int main() {
	int n, a[100];
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
		scanf("%d", &a[i]);
	merge_sort(a, 0, n - 1);
	for (int i = 0; i < n; ++i)
		printf("%d ", a[i]);
	return 0;
}

注：本文参考自课程ppt