算法（第4版）
Overview
第1章 基础
本书对基础这块笔墨非常多，第1章就有150页之多，简洁利落的介绍了本书所涉及Java程序的基础、数据抽象，基本数据结构。同时，也讲解了分析和比较算法的基本原则和方法。本书作者非常用心，适合初学者或者基础薄弱的童鞋入门。
基础编程模型
本书使用Java语言来实现算法，这么做的原因如下：
- 程序是对算法精确、优雅和完全的描述
- 可以通过运行程序来学习算法的各种性质
- 可以在应用程序中直接使用这些算法
相比使用自然语言描述这些优势是重要而巨大的。但使用某一具体的语言也存在缺点，这会使分离算法的思想和实现细节变得困难，所以书中只使用了Java的部分子集功能。
原始数据类型与表达式
Java程序的基本组成
- 原始数据类型 int, double, boolean, char等
- 标识符 a, abc等
- 变量 任意标识符
- 运算符 + - * /
- 字面量
- int 1, 0, -42等
- double 2.0, 1.0e-15等
- boolean true, false
- ...
- 表达式
- int n1+n2/2
- double 1.0e-15 * x
- boolean x <=y
本书常用的原始数据类型
- 整型 int，及其算术运算符
- 双精度实数 double，及其算术运算符
- 布尔 boolean，及其逻辑操作
- 字符串 string
优先级
算术运算：
- /
逻辑运算：
- !
- &&
- ||
类型转换
如果无信息损失，数值会被自动提升为高级的数据类型。（也就是说低精度转高精度可以自动完成）
浮点数转整型将会截断小数部分而非四舍五入。
语句
Java 程序是由语句组成的。语句 能够通过创建和操作变量、对变量赋值并控制这些操作的执行流程来描述运算。通常语句：
- 声明语句
- 赋值语句
- 条件语句
- 循环语句
- 调用和返回语句
简便记法
- 声明并初始化：int i = 1
- 隐式赋值：i++, i--, --i, ++i， i/=2，i +=1
- 单语句代码片段可省略花括号
- for语句
数组
数组能够顺序存储相同类型的多个数据。
1int[] arr0 = {1,2,3,4,5};
2
3double[] arr1 = new double[N];
4
5double []arr2;
6arr2 = new double[N];
起别名
b 是 arr的别名：
1int[] arr = new int[N];
2
3int[] b = arr;
二维数组
M x N 即 M 行长度，长度（列）为 N 的二维数组。 arr[i][j] 表示第i行第j列的元素。
1double[][] arr = new double[M][N];
静态方法
public static 签名开头的方法、函数，与实例方法不是一回事。
递归方法，方法自己调用自己。 我们会经常使用递归，因为递归代码比相应的非递归代码更加简洁优化、易懂。编写递归方法最重要的三点：
- 递归总有一个最简单的情况 --- 方法的第一条语句总是一个包含 return 的条件语句。
- 递归调用总是去尝试解决一个规模更小的子问题，这样递归才能收敛到最简单的情况。
- 递归调用的父问题和尝试解决的子问题之间不应该有交集。
基础编程模型、模块化编程模型、单元测试等
API
应用程序接口编程，方便别人调用。
字符串
字符串拼接： "abc" + "123"
类型转换：parseInt(String s)) 等等方法
自动类型转换：toString() 跟golang类似
输入输出
输入输出的种类很多，最知名且常用的是标准输入、标准输出。
标准输出 System.out ，打印到终端窗口。
标准输入 System.in ，从终端读取数据。
重定向 a > b a 重定向到 b。
重定向 a < b b 重定向到 a。比如：wc -l < data.txt。
管道 a | b 将a的标准输出当做a的标准输入。
基于文件的输入输出。
图像输出。
二分查找（折半查找），基础中的基础了吧。
数据抽象
数据类型指的是一组值和一组对这些值操作的集合，定义和使用数据类型的过程被称为数据抽象。
Java 是面向对象的语言，使用 class 关键字构造被称为引用类型的数据类型。在 Java 中你可以定义自己的数据类型抽象任意对象。
我们使用 API 来说明抽象数据类型的行为，抽象数据类型可以继承父类的方法。
创建对象的过程：
- 为新对象分配内存空间
- 调用构造函数初始化对象的值
- 返回该对象的一个引用
赋值语句：使用引用类型的赋值语句将会创建该引用的一个副本，赋值不会创建新的对象，其实就是别名。
抽象数据类型（class）的组成：
- 实例变量
- 构造函数
- 实例方法
- 静态方法
数据类型的设计
- 封装
- 设计 API
- 接口继承
- 实现继承
两个对象相等意味着什么？ 等价性关系：
- 自反性 x.equals(x) true
- 对称性 x.equals(y) true，y.equals(x) true
- 传递性 x.equals(y) true，z.equals(y) true
- 一致性 x,y未变动，x.equals(y)始终如一
- 非空性 x.equals(null) 总是false
内存管理（垃圾回收）
Java 最重要的特性就是自动内存管理。它通过记录孤儿对象，并将它们的内存释放到内存池中，将程序员从管理内存的责任中解放出来。
不可变性
不可变数据类型，该类型的对象中的值在创建之后就无法再被改变。通过 final 修饰符来强制保证不可变性。缺点：
- 需要为每个值创建一个新对象。
- 只能保证原始数据类型的实例变量的不可变，无法用于引用类型的变量。
异常
不受程序员控制的不可预见的错误。
断言
验证我们在代码中做出的一些假设。
错误
程序错误？