算法基础。

基础编程模型

要创建静态方法库和定义数据类型,会用到以下几种语法,它们是 JAVA 的基础,是现代大多数语言共有的特性:

  • 原始数据类型
  • 语句:包括声明、赋值、条件、循环、调用和返回
  • 静态方法:封装并重用代码
  • 字符串
  • 标准输入/输出
  • 数据抽象:帮助定义非原始数据类型,进而支持面向对象

从 algs4.cs.princeton.edu 下载 algs4.jar,书中为本书封装了标准库协助学习,如:

  • 随机数静态方法库 StdRandom
  • 数据分析静态方法库 StdStats
  • 标准输入库 StdOut,标准输入库 StdIn
  • 标准会图库 StdDraw

测试数据:从 algs4.cs.princeton.edu 下载 algs4-data.zip

从二分查找看算法

以下是一段经典的二分查找算法

 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
import java.util.Arrays;

public class BinarySearch {

  // 数组 a 是有序的
	public static int rank(int key, int[] a) {
    int lo = 0;
    int hi = a.length - 1;
    while(lo <= hi) {
      // 被查找的键要么不存在,要么必然存在于 a[lo...hi]之中
      int mid = lo + (hi -lo) / 2;
      if (key < a[mid]) hi = mid - 1;
      else if (key > a[mid]) lo = mid + 1;
      else return mid;
    }
    return -1;
  }

  public static void main(String[] args) {

    // read the integers from a file
    In in = new In(args[0]);
    int[] whitelist = in.readAllInts();

    // sort the array
    Arrays.sort(whitelist);

    // read integer key from standard input; print if not in whitelist
    while (!StdIn.isEmpty()) {
      int key = StdIn.readInt();
      if (rank(key, whitelist) < 0)
        StdOut.println(key);
    }
  }
}

该程序接收一个白名单文件(一列整数),过滤掉标准输入中所有存在白名单的条目,将不存在白名单的条目输出到标准输出中。

开发用例

针对算法的实现,开发用例 main() 函数,该程序的 main 函数从命令行指定文件读取多个整数,再打印出标准输入中不存在该文件中的整数,通过较小的测试文件测试其行为,使用较大的文件测试算法的性能。

性能

以下 rank 函数的实现十分简单,但其效率非常慢,当数据到达一定规模时,基本不可用,因此,后续着重算法的性能研究:

1
2
3
4
5
6
public static int rank(int key, int[] a) {
  for (int i = 0; i < a.length; i++) {
    if (a[i] == key) return i;
  }
  return -1;
}

数据抽象

拥抱数据抽象的原因有三:

  • 允许通过模块化编程复用代码
  • 使轻易构造多种所谓的链式数据结构
  • 准确定义算法问题

使用抽象数据类型

抽象数据类型(ADT)是一种对使用者隐藏数据表示的数据类型,其将数据类型和函数实现关联,使用者不需要关注它是如何实现的,更多注意力集中在其 API 描述的操作上,使得能够通过它们:

  • 以适用于各种用途的 API 形式准确定义问题
  • 以 API 的实现描述算法和数据结构

以下以封装计算器 Counter 的 API 为例:

public class Counter
Counter(String id); 构造函数,创建名为 id 的计数器
void increment(); 将计数器的值 +1
int tally(); 统计 +1 的次数
String toString(); 对象的字符串表示

可以通过构造函数 Counter(),实例方法 increment(),tally(),以及继承的 toString() 方法使用Counter 数据类型。

对象

对象是能够承载数据类型的值的实体,所有对象都有三大特性:

  • 状态:数据类型中的值
  • 标识:对象区别于其它对象的标志,可以理解为内存中的位置的区别
  • 行为:数据类型的操作

当调用 new 创建对象时,系统都会:

  • 为新对象分配内存空间
  • 调用构造函数初始化对象中的值
  • 返回该对象的一个引用