【Algorithm学习笔记3】2017.07.19 终于到排序了…

2.1 初级排序算法

2.1.1游戏规则

2.1.2 选择排序

方法:找最小,和第一个换位置;找剩下的最小,和第二个换位置。如此反复,直到最后一个数。
效率:长度为N的数组,N次交换,(N*N)/2次比较
缺点:输入的初始状态对运行时间无关
优点:移动次数最少

2.1.3 插入排序

方法:一张一张,每一张插入已经有序的适当位置,插入位置右边所有元素向右移动一位,给插入元素腾出空间。
效率:长度为N的数组,平均(N*N)/4次交换,(N*N)/4次比较;最差(N*N)/2次交换,(N*N)/2次比较;最好0次交换,(N-1)次比较
优点:对部分有序数列十分高效

【Algorithm学习笔记2】2017.06.14

1.1.7 API
java.lang中有Math库
java.util.Arrays库中有sort
哪些库需要import?哪些不需要?
API的目的是将调用和实现分离。
1.1.8 字符串
 
1.1.8.1 字符串拼接
1.1.8.2 类型转换
Integer.parseInt
Integer.toString
Double.parseDouble
Double.toString
1.1.8.3 自动转换
加号一个参数是String,Java自动将其他转换为String
“”可以任意转换为String
1.1.8.4 命令行参数
1.1.9 输入输出
1.1.9.1 命令和参数
1.1.9.2 标准输出
1.1.9.3 格式化输出
StdOut.printf()
1.1.9.4 标准输入
1.1.9.5 重定向与管道
1.1.9.6 基于文件的输入输出
1.1.10 二分查找

【Algorithm学习笔记1】2017.05.28

1.1.1 Java程序的基本结构
【不懂】
要执行一个Java程序,首先要用javac命令编译它,然后再用java命令运行它。例如运行BinarySearch,首先要输入javac BinarySearch.java(这将生成一个叫BinarySearch.class的文件,其中含有这个程序的java字节码);然后再输入java BinarySearch(接着是一个白名单文件名)把控制权移交给这段字节码程序。
1.1.2 原始数据类型与表达式
原始数据类型:int,double,boolean,char
int值域:-2^31至+2^31-1之间,32位,二进制补码
int运算符:加,减,乘,除,求余
double值域:双精度实数,64位,IEEE754标准
boolean运算符:&&(and),||(or),!(not),^(nor)
char值域:字符,16位
运算符优先级:*,/,%      >>>>>    +,-
                         !>>> && >>> ||
数据类型转换:如果不会损失信息,数值会被自动提升为高级的数据类型。double to int 会截断小数部分,而不是四舍五入
其他原始类型:long(64位整数),short(16位整数),byte(8位整数),float(32位单精度实数)
1.1.3 语句
1.1.4 简便记法
如果条件语句或循环语句的代码段只有一条语句,{}可以省略
1.1.5 数组
1.1.5.1 创建并初始化数组
  1. 声明数组的名字和类型
  2. 创建数组:需要指定数组长度(元素个数),关键字:new
  3. 初始化数组元素
明确的创建数组的原因是Java编译器在编译时无法知道应该为数组预留多少空间
double[] a; 声明数组a
a = new double[N]; 创建数组a
for (int i = 0; i < N; i ++) 初始化
    a[i] = 0.0
1.1.5.2 简化写法
double[] a = new double[N] 声明+创建+默认初始值
int[] a = {1,1,2,3,5,8} 声明+创建+赋值初始值
double类型的变量的默认初始值都是0.0
布尔型的默认初始值都是false
1.1.5.3 使用数组
数组一经创建,大小就是固定的
1.1.5.4 起别名
如果将一个数组变量赋予给另一个变量,那么两个变量将会指向同一个数组。
想将数组复制,应重新声明、创建并初始化一个数组,将原数组中的值一一赋予新数组的值。
1.1.5.5 二维数组
1.1.6 静态方法
静态方法是一组在调用时会被顺序执行的语句。
签名 + 函数体
签名 = public static + 函数返回值 + 方法名 + 各种类型参数
递归:三点
  1. 总有一个最简单情况——第一条总是一个包含return的条件语句
  2. 总是去解决一个规模更小的子问题,这样才能收敛到最简单情况
  3. 调用的父问题和解决的子问题之间不能有交集
使用递归简洁易懂,且可以用数学估计程序性能(计算复杂度)
静态方法库是Java类中的一组静态方法
类的声明是public class  + 类名 + {静态方法}
存放类的文件的文件名和类名相同,扩展名是 .java