Chapter 1 基础
基础编程模型
终端命令详解
| 命令 | 参数 | 作用 |
|---|---|---|
| javac | .java文件名 | 编译java程序 |
| java | .class文件名和命令行参数 | 运行java程序 |
| more | 任意文本文件名 | 打印文件内容 |
eg: % java RandomSeq 5 100.0 200.0
- %: 提示符
- java: 调用java
- RandomSeq: 调用该类的静态方法
- 5: args[0]
- 100.0: args[1]
- 200.0: args[2]
Union-Find算法
动态连通性
API
Quick-Find
1 | public class UF |
- 缺点：所有的子节点记录的都是其所属树的根节点，当某棵树变成一棵子树之后，其所有的子节点都将逐一遍历替换记录值
Quick-Union
1 | private int find(int p) |
- 优点：每个节点的记录值将是所属父节点，解决了Quick-Find算法的不足
- 缺点：不同树合并时可能会造成一头轻一头重的“畸形树”
Weighted Quick-Union
1 | for (int i = 0; i < N; i++) |
Weighted Quick-Union With Path Compression
- 上述的算法证明树的理想高度为1，即一棵十分扁平的树，因此可以使用路径压缩的方式进行优化
1 | private int find(int p) |
时间复杂度分析
| Algorithm | Constructor | Union | Find |
|---|---|---|---|
| Quick-Find | N | N | |
| Quick-Union | N | Tree height | Tree height |
| Weighted Quick-Union | N | lgN | lgN |
| Weighted Quick-Union With Path Compression | N | Very near to 1 (amortized) | Very near to 1 (amortized) |
References
Chapter 2 排序
Selection 选择排序
思想
找到数组中的最小元素，然后将它与数组的第一个元素交换位置。然后再从剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。
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
61package chapter2;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
public class Selection {
public static void sort(Comparable[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
int min = i;
for (int j = i + 1; j < N; j++) {
if (less(a[j], a[min]))
min = j;
exch(a, i, min);
}
}
}
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
StdOut.print(a[i] + " ");
StdOut.println();
}
}
public static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++) {
if(less(a[i], a[i - 1]))
return false;
}
return true;
}
public static void main(String[] args) {
//String[] a = In.readStrings(); 方法过时
String[] a = new In("F:\\IntelliJ IDEA 2018.1.4\\my_workspace\\Algorithms_4th\\algs4-data\\tiny.txt").readAllStrings();
sort(a);
/*
assert 断言
（1）assert [boolean 表达式]
如果[boolean表达式]为true，则程序继续执行。
如果为false，则程序抛出AssertionError，并终止执行。
（2）assert[boolean 表达式 : 错误表达式 （日志）]
如果[boolean表达式]为true，则程序继续执行。
如果为false，则程序抛出java.lang.AssertionError，输出[错误信息]。
*/
assert isSorted(a); //检测是否排序正确
show(a);
}
}
特点
- 运行时间和输入无关。为了找出最小的元素而扫描一遍数组并不能为下一遍扫描提供信息
- 数据移动是最小的。每次交换都会改变两个数组的元素的值，因此选择排序用了N次交换
- 最坏情况时间复杂度 O(n^2)
- 最好情况时间复杂度 O(n^2)
- 平均情况时间复杂度 O(n^2)
Insertion 插入排序
思想
将一个元素插入到已排序的数组中，使得插入之后的数组也是有序的。插入排序从左到右插入每个元素，每次插入之后左部的子数组是有序的。
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
49package chapter2;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
public class Insertion {
public static void sort(Comparable[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
exch(a, j, j-1);
}
}
}
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
StdOut.print(a[i] + " ");
StdOut.println();
}
}
public static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++) {
if(less(a[i], a[i - 1]))
return false;
}
return true;
}
public static void main(String[] args) {
String [] a = new In("F:\\IntelliJ IDEA 2018.1.4\\my_workspace\\Algorithms_4th\\algs4-data\\tiny.txt").readAllStrings();
sort(a);
assert isSorted(a);
show(a);
}
}
特点
- 最坏情况时间复杂度 O(n^2)
- 最好情况时间复杂度 O(n)
- 平均情况时间复杂度 O(n^2)
Shell 希尔排序
思想
希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。换句话说，一个h有序数组就是h个互相独立的游戏数组编织在一起组成的一个数组。在进行排序是，如果h很大，我们能将元素移动到很远的地方，为实现更小的h有序创造方便。用这种方式，对于任意为1结尾的h序列，我们能够将数组排序，这就是希尔排序。
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
53package chapter2;
import edu.princeton.cs.algs4.StdOut;
public class Shell {
public static void sort(Comparable[] a) {
int N = a.length;
int h = 1;
while (h < N/3)
h = 3 * h + 1;
while (h >= 1) {
for (int i = h; i < N; i++) {
for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
exch(a, j, j-h);
}
}
h = h/3;
}
}
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
StdOut.print(a[i] + " ");
StdOut.println();
}
}
public static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++) {
if(less(a[i], a[i - 1]))
return false;
}
return true;
}
public static void main(String[] args) {
String [] a = {"3", "1", "2"};
sort(a);
assert isSorted(a);
show(a);
}
}
特点
- 最坏情况时间复杂度 O(n^2)
- 最好情况时间复杂度 O(nlogn)
- 平均情况时间复杂度 O(n√n)
Merge Top-Down 归并排序 自顶向下
思想
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide AND Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
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
69package chapter2;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
public class MergeTopToDown {
private static Comparable[] aux;
public static void sort(Comparable[] a) {
aux = new Comparable[a.length];
sort(a, 0, a.length-1);
}
public static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) return;
int mid = lo + (hi - lo)/2;
sort(a, lo, mid);
sort(a, mid+1, hi);
merge(a, lo, mid, hi);
}
private static void merge(Comparable[] a, int lo, int mid, int hi) {
int i = lo, j = mid+1;
for(int k = lo; k <= hi; k++)
aux[k] = a[k];
for (int k = lo; k <= hi; k++)
if (i > mid)
a[k] = aux[j++];
else if (j > hi )
a[k] = aux[i++];
else if (less(aux[j], aux[i]))
a[k] = aux[j++];
else
a[k] = aux[i++];
}
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
StdOut.print(a[i] + " ");
StdOut.println();
}
}
public static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++) {
if(less(a[i], a[i - 1]))
return false;
}
return true;
}
public static void main(String[] args) {
String [] a = {"3", "1", "2"};
sort(a);
assert isSorted(a);
show(a);
}
}
特点
- 最坏情况时间复杂度 O(nlogn) (typical)
- 最好情况时间复杂度 O(nlogn)
- 平均情况时间复杂度 O(nlogn)
Merge Down-Top 归并排序 自底向上
思想
实现归并排序的另一种方法是先归并那些微型数组，然后再成对归并得到的子数组，如此这般，知道我们将整个数组归并在一起。这种方法比标准的递归方法所需要的代码量更少。
首先我们两两归并（把每个元素想象成一个大小为1的数组），然后四四归并（将两个大小为2的数组归并成一个有4个元素的数组），然后八八归并，一直下去。在每一轮归并中，最后一次归并的第二个子数组可能比第一个子数组要小（但这对merge()方法不是问题），如果不是的话所有的归并中两个数组大小都应该一样，而在下一轮中子数组的大小会翻倍。
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
65package chapter2;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
public class MergeDownToTop {
private static Comparable[] aux;
public static void sort(Comparable[] a) {
int N = a.length;
aux = new Comparable[N];
for (int sz = 1; sz < N; sz = sz + sz) { // sz子数组对的大小
for (int lo = 0; lo < N - sz; lo += sz + sz) { // lo 子数组的索引
merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}
}
}
private static void merge(Comparable[] a, int lo, int mid, int hi) {
int i = lo, j = mid+1;
for(int k = lo; k <= hi; k++)
aux[k] = a[k];
for (int k = lo; k <= hi; k++)
if (i > mid)
a[k] = aux[j++];
else if (j > hi )
a[k] = aux[i++];
else if (less(aux[j], aux[i]))
a[k] = aux[j++];
else
a[k] = aux[i++];
}
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
StdOut.print(a[i] + " ");
StdOut.println();
}
}
public static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++) {
if(less(a[i], a[i - 1]))
return false;
}
return true;
}
public static void main(String[] args) {
String [] a = {"3", "1", "2"};
sort(a);
assert isSorted(a);
show(a);
}
}
特点
- 代码量更少
Quick 快速排序
思想
- 快速排序是一种分治的排序算法。它将一个数组分成两个子数组，将两部分独立地排序。 通过”切分”将数组分成两半 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
1 | package chapter2; |
切分函数 partition
- 切分能将切分元素放到一个合适的位置，然后再用递归调用将其他位置的元素排序(一般策略是先随意抽取a[lo]当切分元素) 该方法使得数组满足下面三个条件：
- 对于某个j，a[j]已经排定
- a[lo]到a[j-1]中的所有元素都不大于a[j]
- a[j+1]到a[hi]中的所有元素都不小于a[j]。
算法过程图
三向切分快速排序
思想
- Dijkstra的算法如 ”三向切分的快速排序算法“ 中极为简洁的切分代码所示。它从左到右遍历数组一次，维护一个指针lt使得a[lo.. lt-1]中的元素都小于v，一个指针gt使得a[gt+1..hi]中的元素都大于v，一个指针i使得a[lt..i-1]中的元素都等于v，a[i..gt]的元素还未确定
- 解决数组存在大量重复元素
- a[i]小于v，将a[lt]和a[i]交换，将lt和i加一
- a[i]大于v，将a[gt]和a[i]交换，将gt减一
- a[i]等于v，将i加一
1 | package chapter2; |
算法过程图
特点
- 最坏情况时间复杂度 O(n^2)
- 最好情况时间复杂度 O(nlog2n)
- 平均情况时间复杂度 O(nlog2n)
