算法第四版 练习题记录
仅提供中文版本
课后题并没有全部做,只是挑出几个无法确定或不能想到结果的进行记录
因为之前没有使用过IDEA导致浪费很多时间进行IDE的配置用户调试
算法第四版
算法第一章
题目概要:检索用户输入”[()]{}{[()()]}”进行相应符号的配对,如果符号无法匹配输出false
思路,参考之前书中提到过的算术表达式求值(P79) 通过创建下压栈lops进行记录左侧符号,包含[ { (,如果在读取语句中遇到右侧符号] } ),lops.pop()弹出栈上最上面的值,如果不是左右匹配则输出错误,直至全部循环结束
== 由于jar包里面的类加上IDE使用不熟悉,所以没有进行语句的全部录入并拆解 ==
code
1 | public class MainProject { |
算法(第四版) 2.2 自上而下的归并排序算法
利用周末将上班日看的算法进行练习,复原算法,果然周一看的已经忘得差不多了,通过再次复原算法的每一步,理清思路再与后面书中的步骤进行对照:smile:
code
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
64public static void main(String[] args) {
String[] a=new String[]{"A","E","Q","S","U","Y","E","I","N","O","S","T"};
Merga.sort(a);
Merga.show(a);
}
public static class Merga{
private static Comparable[] aux;
public static void merge(Comparable[] a ,int lo,int mid,int hi){
int i=lo;
int j=mid+1;
for(int k=lo;k<=hi;k++){
aux[k] = a[k];
}
//此处进行全部数组的遍历,最小值为:lo 最大值:hi
for(int k=lo;k<=hi;k++){
if(i>mid) a[k]=aux[j++]; //1. 当lo>mid时 取右半边元素 此时a[k]=a[j] j自加
else if(j>hi) a[k]=aux[i++];//2. 当mid+1>hi时 取左半边元素 此时a[k]=a[i] i自加
else if(less(aux[j],aux[i])) a[k]=aux[j++];//3. 将a[j]<a[i]时,a[k]=a[j] j自加
else a[k]=aux[i++];//4. 反之,a[k]=a[i] i自加
}
/*
循环的意思为:
当左半区域第一位与右半区域第一位进行比较如果右侧大于左侧,则互换位置
此时i不停自加,当i的值大于mid中间值的时候代表左侧区域值全部取完,此时取右侧元素
j同理
*/
// StdOut.print("Merga -- lo:"+lo+" mid: "+mid+" hi: "+hi+"\r\n");
}
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;
StdOut.print("TT -- lo:"+lo+" mid: "+mid+" hi: "+hi+"\r\n");
sort(a,lo,mid);//此处递归值,将从0,5,11依次递减至0,0,1停止,此时运行第二个递归将从0,0,1开始,第二个递归接收值使用hi<lo直到0,2,5
StdOut.print("First Sort -- lo:"+lo+" mid: "+mid+" hi: "+hi+"\r\n");
sort(a,mid+1,hi);//此处递归值,有人前期可能会理解为统一层面,不明白hi为何会一直变化,他发挥作用其实是在a,lo,mid的值
StdOut.print("Second Sort -- lo:"+lo+" mid: "+mid+" hi: "+hi+"\r\n");
merge(a,lo,mid,hi);
/*
由于此结构相当于三层递归,所以会产生一定的理解误差,第二个sort函数sort(a,mid+1,hi)其实一直在第一个函数之下,可以理解成
sort(a,lo,mid){sort(a,mid+1,hi)},通过将满足的数组不断遍历 从而比较大小进行互换
*/
}
private static boolean less(Comparable v,Comparable w){
return v.compareTo(w)<0;
}
private static void show(Comparable[] a ){
for(int i=0;i<a.length;i++){
StdOut.print(a[i]+" ");
}
StdOut.println();
}
private static boolean isSorted(Comparable[] a){
for(int i=1;i<a.length;i++)
if(less(a[i],a[i-1])) return false;
return true;
}
}Merga方法
1 | # Java |
sort自我遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15# Java
public static void sort(Comparable[] a ,int lo,int hi){
if(hi<=lo) return;
int mid = lo+(hi-lo)/2;
StdOut.print("TT -- lo:"+lo+" mid: "+mid+" hi: "+hi+"\r\n");
sort(a,lo,mid);//此处递归值,将从0,5,11依次递减至0,0,1停止,此时运行第二个递归将从0,0,1开始,第二个递归接收值使用hi<lo直到0,2,5
StdOut.print("First Sort -- lo:"+lo+" mid: "+mid+" hi: "+hi+"\r\n");
sort(a,mid+1,hi);//此处递归值,有人前期可能会理解为统一层面,不明白hi为何会一直变化,他发挥作用其实是在a,lo,mid的值
StdOut.print("Second Sort -- lo:"+lo+" mid: "+mid+" hi: "+hi+"\r\n");
merge(a,lo,mid,hi);
/*
由于此结构相当于三层递归,所以会产生一定的理解误差,第二个sort函数sort(a,mid+1,hi)其实一直在第一个函数之下,可以理解成
sort(a,lo,mid){sort(a,mid+1,hi)},通过将满足的数组不断遍历 从而比较大小进行互换
*/
}此处的值为
1 | TT -- lo:0 mid: 5 hi: 11 |
通过值可以清晰的看出递归的层次结构,最终将简化为针对小数组进行互换,最后与书中实例讲解比对一下,自己理解没有出现很大的误差,算是重新复习一下
算法(第四版) 2.3 快速排序
快速排序时选出一个基准参数,就开那个数组进行怕排序,左侧指针小于基准,右侧大于基准,三向快速排序中还会增加等于基准指针的值
与2.2归并排序的思路一致,通过对数组的不断递归,逐步将左侧和右侧进行排序得出结果
code:
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
37public static class Quick{
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 lt=lo,i=lo+1,gt=hi;
Comparable v = a[lo];//随机值,设置数组起点
while(i<=gt){
int cmp = a[i].compareTo(v);
if(cmp<0) exch(a,lt++,i++);//如果a[i]<a[lo] 交换a[lt]-->a[lo]与a[i]-->a[lo+1],相应参数运算后自加
else if(cmp>0) exch(a,i,gt--);//反之,交换a[i]与a[gt],当道第三个指针中,gt自减~指针左移,转换位置之后i不变再次循环将继续判断a[i]
else i++;
StdOut.print("while statement lt: "+lt+" i:"+i+" gt:"+gt+"\r\n");
}
sort(a,lo,lt-1);//运行完第一次之后,将划分为三段<a[lo];=a[lo];>a[lo],此时针对,a[lo]部分进行排序,逐步递归,将左侧区域位置变为有序数组
StdOut.print("second lo:"+lo+" lt:"+lt+"\r\n");
sort(a,gt+1,hi);
StdOut.print("third gt:"+gt+" hi:"+hi+"\r\n");
}
private static void exch(Comparable[] a ,int lo,int hi){
Comparable tmp ;
tmp=a[lo];
a[lo]=a[hi];
a[hi]=tmp;
}
private static void show(Comparable[] a ){
for(int i=0;i<a.length;i++){
StdOut.print(a[i]+" ");
}
StdOut.println();
}
}输出:
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
50while statement lt: 0 i:1 gt:10
while statement lt: 0 i:1 gt:9
while statement lt: 0 i:1 gt:8
while statement lt: 0 i:1 gt:7
while statement lt: 0 i:1 gt:6
while statement lt: 0 i:1 gt:5
while statement lt: 0 i:1 gt:4
while statement lt: 0 i:1 gt:3
while statement lt: 0 i:1 gt:2
while statement lt: 0 i:1 gt:1
while statement lt: 0 i:1 gt:0
second lo:0 lt-1:-1
while statement lt: 1 i:2 gt:10
while statement lt: 2 i:3 gt:10
while statement lt: 2 i:3 gt:9
while statement lt: 2 i:3 gt:8
while statement lt: 2 i:3 gt:7
while statement lt: 3 i:4 gt:7
while statement lt: 3 i:4 gt:6
while statement lt: 4 i:5 gt:6
while statement lt: 5 i:6 gt:6
while statement lt: 6 i:7 gt:6
while statement lt: 1 i:2 gt:4
while statement lt: 1 i:2 gt:3
while statement lt: 1 i:3 gt:3
while statement lt: 1 i:3 gt:2
second lo:1 lt-1:0
while statement lt: 4 i:5 gt:5
while statement lt: 4 i:5 gt:4
second lo:3 lt-1:3
third gt+1:5 hi:5
third gt+1:3 hi:5
second lo:1 lt-1:5
while statement lt: 8 i:9 gt:11
while statement lt: 9 i:10 gt:11
while statement lt: 10 i:11 gt:11
while statement lt: 11 i:12 gt:11
while statement lt: 7 i:8 gt:9
while statement lt: 7 i:9 gt:9
while statement lt: 7 i:9 gt:8
second lo:7 lt-1:6
while statement lt: 10 i:11 gt:10
second lo:9 lt-1:9
third gt+1:11 hi:10
third gt+1:9 hi:10
second lo:7 lt-1:10
third gt+1:12 hi:11
third gt+1:7 hi:11
third gt+1:1 hi:11
All articles on this blog are licensed under CC BY-NC-SA 4.0 unless otherwise stated.
