一 排序
1 冒泡排序
简单来说就是，重复走访要排序的数列，一次比较两个元素，如果顺序错误，就调换过来
算法步骤
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
示例：对{3,1,6,2,5}从小到大排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 3 1 6 2 5
第一次循环：
1) 1 3 6 2 5
2) 1 3 6 2 5
3) 1 3 2 6 5
4) 1 3 2 5 6 比较4次
1 3 2 5
第二次循环：
1) 1 3 2 5
2) 1 2 3 5
3) 1 2 3 5 比较3次
1 2 3
第三次循环：
1) 1 2 3
2) 1 2 3 比较2次
1 2
第四次循环：
1) 1 2 比较1次
|
总结：走访次数=数组个数-1
代码部分
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
| public class BubbleSort {
public static void main(String[] args) {
int[] arrays = new int[]{2, 4, 1, 3, 8, 5, 9, 6, 7};
int temp = 0;
boolean flag = false;
for (int i = 0; i < arrays.length - 1; i++) {
for (int j = 0; j < arrays.length - 1 - i; j++) {
if (arrays[j] > arrays[j + 1]) {
flag = true;
temp = arrays[j];
arrays[j] = arrays[j + 1];
arrays[j + 1] = temp;
}
}
if (!flag) {
break;
} else {
flag = false;
}
}
System.out.println(Arrays.toString(arrays));
}
}
|
2 选择排序
这是一种简单直观的排序算法，无论什么数据输入都是O(n2)。所以用到的数据规模越小越好。
算法步骤
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
示例：对{3,1,6,2,5}从小到大排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| 选择排序比冒泡排序的效率高
高在交换位置的次数上。
循环一次，然后找出参加比较的这堆数据中最小的，拿着这个最小的值和
最前面的数据"交换位置"
参与比较的数据：3 1 6 2 5 这一堆数据最左边下标为0
第1次循环之后的结果是：
1 3 6 2 5
参与比较的数据：3 6 2 5 这一堆数据最左边下标为1
第2次循环之后的结果是：
2 6 3 5
参与比较的数据：6 3 5 这一堆数据最左边下标为2
第3次循环之后的结果是：
3 6 5
参与比较的数据：6 5 这一堆数据最左边下标为3
第4次循环之后的结果是：
5 6
注意：5条数据，循环4次
|
代码部分
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
| public class SelectSort {
public static void main(String[] args) {
int[] arr = {3, 1, 6, 2, 5};
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
if (min != i) {
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
|
3 快速排序
快速排序是对冒泡排序的一种改进。将要排序的数据分割成独立的两部分，其中一部分的数据都比另一部分所有的数据小，之后按照此方法递归至有序序列。
快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
算法步骤
- 从数列中挑出一个元素，称为 “基准”（pivot）;
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
4 插入排序
二 分治法
2.1 算法思想
先“分”后“治”，将复杂的问题分成若干个相同或相似的子问题…知道最后子问题可以简单的直接求解，原问题的解即子问题的解。
2.2 三大步骤
- 分解：原问题分解为若干规模较小，相互独立，与原问题结构相似的子问题
- 求解：若子问题规模较小容易则直接求解，否则递归的解决各个子问题。
- 合并：合并子问题解。
2.3 时间复杂度计算方法
表示把规模为n的问题分成k个规模为n/m的小问题，得：
计算步骤：
①令$\frac{n}{m^x}=1$，解出$x=log_mn$
②$T(n)=O(k^x+xf(n))$去最高次幂
2.1 二分查找
2.1.1 算法思路
基本思想：
首先确定该数组的中间下标，mid=(left+right)/2
然后让需要找的数x和数组A[mid]作比较，有三种情况
（1）x>A[mid]，数x在mid右边，递归右查找
（2）x<A[mid]，数x在mid左边，递归左查找
（3）x=A[mid]，找到了，返回下标
递归停止条件：
（1）找到数字就返回下标
（2）如果递归完整个数组，当left>right就结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int binarySearch(int[] A,int x,int len){
int left = 0,right=len-1;
while(left<=right){
if(x==A[mid])
return mid;
if(x>A[mid])
left=mid+1;
if(x<A[mid])
right=mid-1;
}
return -1;
}
int main(){
int A[]=(1,5,9,11,12,31,57,89);
cout<<binarySearch(A,1,8);
return 0;
}
|
2.1.2 时间复杂度
计算如下：
$\frac{n}{2^x}=1，则x=log_2n；\T(n)=O(1^x+O(1))=O(log_2n)$
2.2 乘法
2.2.1 大整数乘法
有X、Y是n位二进制数，计算X、Y的乘积
当n过大的时候，乘操作消耗$n^2$的资源、加操作消耗2n的资源。如果少一些乘操作，多一些加操作，算法性能会提高。
算法思想
方式一：
$X·Y=AC·2^n+(AD+BC)·2^{\frac{n}{2}}+BD\4次\frac{n}{2}位乘法，3次不超过2n位的加法。$
时间复杂度：
方式二：
$X·Y=AC·2^n+[(A-B)(D-C)+AC+BD)]·2^{\frac{n}{2}}+BD\3次\frac{n}{2}位乘法，6次不超过2n位的加法。$
2.2.2 矩阵相乘
有A、B是n阶方阵，计算矩阵A、B的乘积
当位数n过大时，乘操作消耗n的指数倍资源，加操作消耗n的线性倍资源。
算法思想
方式一：
方式二：
$7次\frac{n}2位乘法$
时间复杂度：
2.3 棋盘覆盖
2.3.1 算法思路
①将当前棋盘4等分
②把当前棋盘最中间的位置、且没有特殊点的位置，覆盖成L型
③重复①、②
2.3.2 执行过程
2.3.3 代码
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| #include "iostream"
using namespace std;
int t = 1;
int Board[100][100];
void cheseBoard(int tr, int tc, int dr, int dc, int size) {
if (size == 1)
return;
int title = t++;
size /= 2;
if (dr < tr + size && dc < tc + size)
cheseBoard(tr, tc, dr, dc, size);
else {
Board[tr + size - 1][tc + size - 1] = title;
cheseBoard(tr, tc, tr + size - 1, tc + size - 1, size);
}
if (dr < tr + size && dc >= tc + size)
cheseBoard(tr, tc + size, dr, dc, size);
else {
Board[tr + size - 1][tc + size] = title;
cheseBoard(tc, tr + size, tr + size - 1, tc + size, size);
}
if (dr >= tr + size && dc < tc + size)
cheseBoard(tr + size, tc, dr, dc, size);
else {
Board[tr + size][tc + size - 1] = title;
cheseBoard(tr + size, tc, tr + size, tc + size - 1, size);
}
if (dr >= tr + size && dc >= tc + size)
cheseBoard(tr + size, tc + size, dr, dc, size);
else {
Board[tr + size][tc + size] = title;
cheseBoard(tr + size, tc + size, tr + size, tc + size, size);
}
}
int main() {
cheseBoard(0, 0, 3, 3, 4);
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
cout << Board[i][j] << " ";
}
cout << endl;
}
return 0;
}
|
2.3.4 分析时间复杂度
2.4 归并排序
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
| void mergeSort(int a[], int begin, int end) {
if (begin < end) {
int mid = (begin + end) >> 1;
mergeSort(a, begin, mid);
mergeSort(a, mid + 1, end);
merge(a, begin, end, mid);
}
}
void merge(int a[], int begin, int end, int mid) {
for (int i = 0; i < 10; ++i) {
help[i] = a[i];
}
int left = begin;
int right = mid+1;
int current = begin;
while (left <= mid && right <= end) {
if (help[left] <= help[right])
a[current++] = help[left++];
else
a[current++] = help[right++];
}
while (left <= mid)
a[current++] = help[left++];
}
|
时间复杂度分析：
2.5 快速排序
三 动态规划
1.基本定义
动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。
动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
2.与分治法的异同
相同点：
不同点：
- 动态规划——自下而上、分治法——自上而下
- 动态规划——子问题重叠（相交）、分治——子问题（独立）
3.动态规划要素
1.最优子结构
2.子问题重叠
大问题要用到小问题得求解结果==》建表存储结\==》子问题重叠\==》性能提升
每次求解的问题都是最优解==》最优子结构
4.做题步骤
1.分析最优子结构
==2.建立递归关系（递归公式）==
3.计算最优值（核心代码）
4.构造最优解（转化为友好型输出代码）
3.1 矩阵连乘
有n个矩阵${A_1,A_2,…,A_n}$，他们中任意相邻矩阵是可乘的，求怎么划分能让这n个矩阵乘下来有最小的计算量。
1.解题思路
我们只能从底层往上找，也就是说先找两个最小的，然后再找最小的，直到乘完。
设A[i;j]为矩阵$A_i \cdots A_j$的连乘计算量。
$A_i…A_j$中间一定有某个k让他们的计算量最小。
假设k将式子分成${Ai…A_k}和{A{k+1}…·A_j}$的计算量最小，