算法复习大纲

算法复习大纲

JAVA算法复习大纲

• JAVA算法复习大纲
• • 排序
  • • 选择排序
    • • 编程
    • 插入排序
    • • 编程
    • 冒泡排序
    • • 编程
    • 合并排序
    • • 编程
  • 堆建立
  • 基数排序
  • Union_Find操作
  • • Union
    • Find
  • 递归
  • • 阶层
    • 斐波那契数列
    • 整数幂的计算
  • 递归（2）
  • • 数组主元素
  • 编程
  • 分治
  • • 分治法解最大最小问题的过程
    • 合并排序的分治算法
    • 快速排序
    • 线性选择
  • 分治（2）选择问题
  • • 中值（5个元素为一组）
    • • 例题
  • 贪婪算法
  • • 背包问题
  • 单元最短路径
  • • 狄斯奎诺（Dijkstra）算法
    • 普里姆
    • 克鲁斯卡尔
    • 霍夫曼编码
  • 图
  • • 深度优先DFS
  • • 广度优先BFS
  • 动态规划
  • • 货郎担
    • 多段图最短路径
    • 最长公共子序列
    • 背包问题
  • 时间复杂度

JAVA算法复习大纲

排序

选择排序

5，1，128，96，76，2
（1）1，5，128，96，76，2
（2）1，2，128，96，76，5
（3）1，2，5，96，76，128
（4）1，2，5，76，96，128
（5）1，2，5，76，96，128

选择排序：找到最小的元素，插入到有序区，有序区是没有元素的，插入的时候会交换元素

编程

import java.util.Arrays;public class xuanzepaixu {public static void main(String[] args) {int numbs[] = {5,1,128,96,76,2};selectionSort(numbs);System.out.String(numbs));}public static void selectionSort(int[] numbs){for (int i = 0; i < numbs.length-1; i++) {int min = i;for (int j = i+1; j < numbs.length; j++) {if (numbs[j]<numbs[min]){min=j;}}if (i!=min){int tmp = numbs[i];numbs[i]=numbs[min];numbs[min]=tmp;}}}
}

插入排序

123，45，19，23，634，4
（1）45，123，19，23，634，4
（2）19，45，123，23，634，4
（3）19，23，45，123，634，4
（4）19，23，45，123，634，4
（5）4，19，23，45，123，634

插入排序：插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动

编程

import java.util.Arrays;public class 插入排序 {public static void main(String[] args) {int numbs[] = {123,45,19,23,634,4};InsertionSort(numbs);System.out.String(numbs));}public static void InsertionSort(int[] numbs){for (int i = 0; i < numbs.length-1; i++) {for (int j = i+1; j > 0; j--) {if (numbs[j]<numbs[j-1]){int tmp = numbs[j];numbs[j]=numbs[j-1];numbs[j-1]=tmp;}}}}
}

冒泡排序

5，1，128，96，76，2

(1) 1,5,96,76,2,128

(2) 1,5,76,2,96,128

(3) 1,5,2,76,96,128

(4) 1,2,5,76,96,128

(5) 1,2,5,76,96,128

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

编程

import java.util.Arrays;public class 冒泡排序 {public static void main(String[] args) {int numbs[] = {1,5,96,76,2,128};BubbleSort(numbs);System.out.String(numbs));}public static void BubbleSort(int[] nums){for (int i = 0; i < nums.length-1; i++) {for (int j = 0; j < nums.length-1-i; j++) {if (nums[j]>nums[j+1]){int tmp = nums[j];nums[j]=nums[j+1];nums[j+1]=tmp;}}}}}

合并排序

假定有 8 个元素，第一步，划分为四对，每一对两个元素，用 merge 算法合并成四个有序的序列；第二步，把四个序列划分成两对，用 merge 算法合并成两个有序的序列；最后，再利用merge算法合并成一个有序的序列。

编程

合并两个有序序列，并返回结果

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class 合并排序 {public static void main(String[] args) {List<Integer> A  = new ArrayList<Integer>();A.add(1);A.add(3);A.add(7);A.add(8);List<Integer> B  = new ArrayList<Integer>();B.add(2);B.add(4);B.add(5);B.add(6);List<Integer> C  = merge(A,B);System.out.println(C);}public static List<Integer> merge(List<Integer> A, List<Integer> B){List<Integer> C = new ArrayList<>();int i=0;int j=0;int n = A.size();int m = B.size();while ((i<n)&&(j<m)){if (A.get(i)&(j)){C.(i));i++;}else{C.(j));j++;}}while (i<n){C.(i));i++;}while (j<m){C.(j));j++;}return C;}}

堆建立

4，1，6，3，8，2，10，5，9，11，7

基数排序

例：链表 L 中元素的关键字值分别为：

​ 3097、3673、2985、1358、6138、9135、4782、1367、3684、0139

1. 按关键字中的数字 d1，把 L 中的元素分布到链表情况:

L0	L1	L2	L3	L4	L5	L6	L7	L8	L9
		4782	3673	3684	2985		3097	1358	0139
					9135		1367	6138

把 L0 ~L9 的元素顺序链接到 L 后，L 中的元素顺序如下

​ 4782 3673 3684 2985 9135 3097 1367 1358 6138 0139

2. 按关键字中的数字 d2，把 L 中的元素分布到链表情况:

L0	L1	L2	L3	L4	L5	L6	L7	L8	L9
			9135		1358	1367	3673	4782	3097
			6138					3684
			0139					2985

把 L0 ~L9 的元素顺序链接到 L 后，L 中的元素顺序如下
9135 6138 0139 1358 1367 3673 4782 3684 2985 3097

3. 按关键字中的数字 d3，把 L 中的元素分布到链表情况:

L0	L1	L2	L3	L4	L5	L6	L7	L8	L9
3097	9135		1358			3673	4782		2985
	6138		1367			3684
	0139

把 L0 ~L9 的元素顺序链接到 L 后，L 中的元素顺序如下
3097 9135 6138 0139 1358 1367 3673 3684 4782 2985

4. 按关键字中的数字 d4，把 L 中的元素分布到链表情况:

L0	L1	L2	L3	L4	L5	L6	L7	L8	L9
0139	1358	2985	3097	4782		6138			9135
	1367		3673
			3684

把 L0 ~L9 的元素顺序链接到 L 后，L 中的元素顺序如下
0139 1358 1367 2985 3097 3673 3684 4782 6138 9135

Union_Find操作

find(x)：寻找元素 x 所在集合
union(x,y)：把元素 x 和元素 y 所在集合合并成一个集合

Union

利用该数据结构合并两个集合的情况

图 (a) 表示由集合 {1,3,5,8}, {2,7,10}, {4,6}, {9} 所组成的森林
图 (b) 表示由元素 1 所在集合、与元素 7 所在集合合并的情况

该数据结构的缺点
树的高度可能很大，变成退化树，成为线性表

union(x,y)操作：
若 x 和 y 是当前森林中两棵不同树的根结点，
如果 rank(x) > rank(y) 把 x 作为 y 的父亲
如果 rank(x) < rank(y) 把 y 作为 x 的父亲
如果 rank(x) = rank(y) 把 x 作为 y 的父亲，rank(x) + 1

Find

路径压缩

find(x) 操作时，找到 x 的根结点 y 之后，再沿着 x 到 y 的路径，改变路径上所有结点的父指针，使其直接指向 y

(a) 表示集合 {1,2,3,4}, {5,6,7,8}

b) 表示执行 union(4,6) 之后的结果

递归

阶层

计算阶乘函数 n!
阶乘函数可归纳定义为

递归算法如下：

public class 递归阶层 {public static void main(String[] args) {int n =5;System.out.println(f(n));}public static int f(int n){if(n==0||n==1){return 1;}return n*f(n-1);}
}

斐波那契数列

关系式：

F(1)=F(2)=1；

F(n)=F(n-1)+F(n-2) (n≥3)

递归算法如下：

public class 斐波那契数列 {public static void main(String[] args) {int n = 20;int f = f(n);System.out.println(f);}public static int f(int n){if (n==1||n==2){return 1;}return f(n-1)+f(n-2);}
}

整数幂的计算

递归（2）

数组主元素

 A 是具有 n 个元素的数组，x 是 A 中的一个元素，若 A中有一半以上的元素与 x 相同，就称 x 是数组的主元素。

例：数组 A={1,3,2,3,3,4,3} 中，
元素 3 是该数组的主元素

编程

public int getCandidate(int nums[], int begin, int end ){int j = begin,count = 1;int c = nums[j];while(j<end-1 && count>0) {j++;if(nums[j]==c) {count = count + 1;}else {count = count - 1;}}if(j==end-1 && count>0) {return nums[j];                      //当剩余的时候说明很有可能是组元素，此时我们返回此时下标到验证函数中验证}else if(j==end-1 && count == 0 ) {return 0;                       //返回0代表没有组元素}else {return getCandidate(nums,j,end);      //递归调用}
}

分治

分治法解最大最小问题的过程

分治法解最大最小问题的过程例子：

合并排序的分治算法

算法的实现

merge_sort(Type A[ ], int low, int high){    int mid;if (high > low){    mid = (high – low) / 2;merge_sort(A[ ], low, mid);merge_sort(A[ ], mid + 1, high);merge(A[ ], low, mid, high, high – low);}}       

快速排序

把序列就地划分为两个子序列，使第一个子序列的所有元素都小于第二个子序列的所有元素，不断地进行这样的划分，最后构成 n 个子序列，每个子序列只有一个元素，这时，整个序列就是按递增顺序排序的序列了

枢点元素：

把序列的第一个元素作为枢点元素，重新排列这个序列

void quick_sort(Type A[ ], int low, int high)
{int k;if (low < high) {k = split(A, low, high);quick_sort(A, low, k-1);quick_sort(A, k+1, high);}
}

快速排序下列数字：
8，1，4，9，0，3，5，2，7，6

线性选择

以下数求出第三大需要几次分区

137，96，88，108，17，87，65，35，76，45，66，18

(a)17，18，88，108，137，87，65，35，76，45，66，96

(b)88，66，45，87，65，35，76，96，108，137

以下数求出第五小需要几次分区

8 1 4 9 0 3 5 2 7 6

(a) 2 1 4 5 0 3 6 8 7 9

(b) 2 1 0 3 4 5

© 4

分治（2）选择问题

中值（5个元素为一组）

① 若，直接排序数组，第 k 个元素即为所求元素；否则，转 ②

② 把元素划分为 p = ⌊n / 5 ⌋ 组，每组 5 个元素，不足 5 个元素的那一组不予处理
③ 取每组的中值元素，构成一个规模为 p 的数组 M
④ 对数组 M 递归地执行算法，得到一个中值的中值元素 m
⑤ 把原数组划分成三组，使得大于 m 的元素存放于 P，等于 m 的元素存放于 Q，小于 m 的元素存放于 R
⑥ 如果 | P | > k，对 P 递归地执行算法；否则转 ⑦
⑦ 如果 | P | + | Q | > k，m 就是所选择的元素；否则转8；
⑧ 对 Q 递归地执行算法。

例题

找出下面37个元素的第16大元素；

35, 43, 2, 19, 28, 62, 36, 7, 5, 13, 25, 13, 32, 11, 1, 9, 12, 23, 37, 39, 58, 43, 41, 51, 27, 8, 26, 34, 22, 15, 19, 54, 48, 30, 24, 6, 10

贪婪算法

不断地从问题的 n 个元素中选取一个最优的元素的取值，作为局部解向量中的一个分量，使其既满足约束方程，又使目标函数取极值最快，当 n 个元素的取值均求取之后，解向量就成为完整的向量，它就是问题的解

背包问题

载重量为 M 的背包，重量为、价值为 的物体，1 ≤ i ≤ n，把物体装满背包，使背包内的物体价值最大
物体可以分割的背包问题，及物体不可分割的背包问题，把后者称为 0/1 背包问题

背包问题（可以分割），n=7,m=20的

载重价值12，7，5，19，20，18，13

重量为 4，5，3，9，10，11，18

载重价值	12	7	5	19	20	18	13
重量	4	5	3	9	10	11	18
/	/	/	/	/	/	/	/
平均价值	3	1.4	1.7	2.1	2	1.63	0.72
	☑️			☑️	☑️

价值最大：12+19+2*7=45

单元最短路径

狄斯奎诺（Dijkstra）算法

普里姆

克鲁斯卡尔

霍夫曼编码

WTL算法(一)：

所有根结点相加

WTL=17+32+63+59+122+132+87+254+172+426=1364

WTL算法(二)：

所有叶子结点*层数相加

85 * 2 + 43 * 3 + 44 * 3…

图

深度优先DFS

（先往深的走，走到头了，就后退）栈

广度优先BFS

动态规划

货郎担

由城市 1 出发，经城市 2, 3, 4然后返回1的最短路径长度为：

多段图最短路径

求解图所示的最短路径问题

最长公共子序列

字符串A=xyxxyx B=yxxxy 求最长公共子序列

	空集	x	y	x	x	y	x
空集	0	0	0	0	0	0	0
y	0	0	1	1	1	1	1
x	0	1	1	2	2	2	2
x	0	1	1	2	3	3	3
x	0	1	1	2	3	3	4
y	0	1	2	2	3	4	4

<

<

背包问题

（不可分割）6个物体，重量：4，2，2，1，3，2。价值：3，6，5，4，3，4。载重为8.

	0	1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0	0	0
1	0	0	4	4	4	4	4	4	4
2	0	0	4	4	4	7	7	7	7
3	0	4	4	8	8	8	11	11	11
4	0	4	5	9	9	13	13	13	16
5	0	4	6	10	11	15	15	19	19
6	0	4	6	10	11	15	15	19	19

{0,1,1,1,0,1}

时间复杂度